\(K_ i\)-covers. I: Complexity and polytopes (Q1070249)

In a graph \(G\) a \(K_ i\) is a complete subgraph of size i. A \(K_ i\)-cover of \(G\) is a set \(C\) of \(K_{i-1}'s\) of \(G\) such that every \(K_ i\) in \(G\) contains at least one \(K_{i-1}\) from \(C\). It is proved that the problem of determining whether a general graph has a \(K_ i\)-cover (i\(\geq 2)\) of cardinality \(\leq k\) is NP-complete. For chordal graphs with fixed maximum clique size, the problem is shown to be polynomial. A partial characterization for the \((K_{i-1}-K_ i)\)-incidence polytope is given by some classes of facets for which the separation problem can be solved in polynomial time.