A 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. © 1986.
Ki-covers I: Complexity and polytopes
CONFORTI, MICHELANGELO;
1986
Abstract
A 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. © 1986.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
