標題: The K-r-packing problem
作者: Guruswami, V
Rangan, CP
Chang, MS
Chang, GJ
Wong, CK
應用數學系
Department of Applied Mathematics
關鍵字: matching;K-r-packing;K-r-factor;NP-completeness;chordal graph;split graph;cograph;line graph
公開日期: 2001
摘要: For a fixed integer r greater than or equal to 2, the K-r-packing problem is to find the maximum number of pairwise vertex-disjoint K-r's (complete graphs on r vertices) in a given graph. The K-r-factor problem asks fur the existence of a partition of the vertex set of a graph into K-r's. The K-r-packing problem is a natural generalization of the classical matching problem, but turns out to be much harder for r greater than or equal to 3 - it is known that for r greater than or equal to 3 the K-r-factor problem is NP-complete: for graphs with clique number r [16]. This paper considers the complexity of the K-r-packing problem on restricted classes of graphs. We first prove that for r greater than or equal to 3 the K-r-packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for r = 3. 4 only), line graphs acid total graphs. The hardness result for K-3- packing on chordal graphs answers an open question raised in [6]. We also give (simple) polynomial algorithms for the K-3-packing and the K-r-factor problems on split graphs (this is interesting in light of the fact that K-r-packing becomes NP-complete on split graphs for r greater than or equal to 4), and for the K-r-packing problem on cographs.
URI: http://hdl.handle.net/11536/29916
http://dx.doi.org/10.1007/s006070170039
ISSN: 0010-485X
DOI: 10.1007/s006070170039
期刊: COMPUTING
Volume: 66
Issue: 1
起始頁: 79
結束頁: 89
Appears in Collections:Articles


Files in This Item:

  1. 000167415100004.pdf