The complexity of generalized clique packing (Q1073049)

It is shown that the problem of packing an arbitrary graph by cliques (with possible intersections) is NP-complete. Let G be a graph. \(K_ i\) denotes a complete subgraph on i vertices, called clique. Let \(p_{ij}(G)\) denote the maximum numbers of cliques \(K_ i\) in G such that any two of them intersect in at most j vertices. The generalized \(P_{ij}\) problem can be formulated as follows: Given graph G and integer k, is \(p_{ij}\) greater than k? It is shown that for \(i\geq 3\) and \(1\leq j\leq i-2\) the \(P_{ij}\) problem is NP-complete. This problem remains still NP-complete even in the case of chordal graphs G.