zbMATH — the first resource for mathematics

The \(K_r\)-packing problem. (English) Zbl 0978.05060
Summary: For a fixed integer \(r\geq 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 for 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\geq 3\)—it is known that for \(r\geq 3\) the \(K_r\)-factor problem is NP-complete for graphs with clique number \(r\). This paper considers the complexity of the \(K_r\)-packing problem on restricted classes of graphs.
We first prove that for \(r\geq 3\) the \(K_r\)-packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for \(r= 3, 4\) only), line graphs and total graphs. The hardness result for \(K_3\)-packing on chordal graphs answers an open question raised in [E. Dahlhaus and M. Karpinski, Discrete Appl. Math. 84, No. 1-3, 79-91 (1998; Zbl 0902.68146)]. 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 the \(K_r\)-packing becomes NP-complete on split graphs for \(r\geq 4\)), and for the \(K_r\)-packing problem on cographs.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05B40 Combinatorial aspects of packing and covering
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX Cite
Full Text: DOI