The complexity of generalized clique covering (Q1262127)

A vertex cover of a graph G is a minimal set of vertices of G such that every edge of G contains at least one vertex in the set. The paper studies the following generalized clique cover problem. Let \(c_{ij}(G)\) denote the minimum number of complete graphs \(K_ j\) in G such that every \(K_ i\) in G \((i>j)\) contains at least one such \(K_ j\). Given an input graph G and an integer a, decide whether \(c_{ij}(G)\leq a\). The problem has been known to be NP-complete if \(i=j+1\), for \(j\geq 1\). This result is extended to arbitrary i,j, \(j>j\geq 1\), by generalizing the construction of proof. Moreover, when the input graph is restricted to be chordal (i.e., each cycle of length greater than 3 has some chord) then the NP-completeness of the problem is shown for \(i>j\geq 2\) by reduction from the general problem. (The restricted problem has been settled for \(i=j+1.)\) Finally, a polynomial-time algorithm for chordal graphs, \(j=1\), and fixed i is given whose complexity, however, is exponential in i. It is shown that even this problem becomes NP-complete if i is regarded as part of the input.