Ki-covers I: Complexity and polytopes

AbstractA Ki in a graph is a complete subgraph of size i. A Ki-cover of a graph G(V, E is a set C of Ki − 1's of G such that every Ki in G contains at least one Ki − 1 in C. Thus a K2-cover is a vertex cover. The problem of determining whether a graph has a Ki-cover (i ⩾ 2) of cardinality ⩽k is shown to be NP-complete for graphs in general. For chordal graphs with fixed maximum clique size, the problem is polynomial; however, it is NP-complete for arbitrary chordal graphs when i ⩾ 3. The NP-completeness results motivate the examination of some facets of the corresponding polytope. In particular we show that various induced subgraphs of G define facets of the Ki-cover polytope. Further results of this type are also produced for the K3-cover polytope. We conclude by describing polynomial algorithms for solving the separation problem for some classes of facets of the Ki-cover polytope