Description
For a given hypergraph H=(V,{\cal E}), the Exact Cover problem asks for the existence of a subset {\cal F} \subseteq {\cal E} of hyperedges covering every vertex of V exactly once; Exact Cover is one of Karp's famous list of 21 NP-complete problems.
The NP-complete Efficient Domination (ED) problem for a graph G=(V,E) corresponds to the Exact Cover problem for the closed neighborhood hypergraph of G. It is known that the ED problem is NP-complete for claw-free graphs, for bipartite graphs as well as for chordal graphs. Thus, ED is NP-complete for F-free graphs whenever F contains an induced subgraph isomorphic to claw or a chordless cycle C_k with k vertices, k \ge 3. If F is claw-free and cycle-free then F is the disjoint union of paths (called a linear forest). From a standard reduction, it follows that ED is even NP-complete for 2P_3-free chordal graphs and thus also for P_7-free chordal graphs. For P_6-free graphs, the complexity of ED is unknown; for all other linear forests F, ED is either NP-complete or solvable in polynomial time.
It is well known that the ED problem on a graph G=(V,E) can be reduced to the Maximum Weight Independent Set (MWIS) problem on the square G^2=(V,E^2) with xy \in E^2 for x \neq y if and only if the G-distance of x and y is at most 2.
Our new results are the following:
(1) For P_5-free graphs, ED can be solved in linear time using modular decomposition.
(2) Squares of P_6-free chordal graphs are chordal; this even holds for the larger class of (P_6,house,hole,domino)-free graphs. Thus, ED is solvable in polynomial time for such graphs.
(3) Using the Strong Perfect Graph Theorem by Chudnovsky et al., we have shown that squares of (P_6,house)-free graphs ((P_6,bull)-free graphs, respectively) are perfect graphs. Thus, ED is solvable in polynomial time for these graphs.
(4) Using a similar approach, we have shown that ED is solvable in polynomial time for (P_6,net)-free graphs. The complexity of ED for P_6-free graphs remains an open problem.
(Joint work with Elaine Eschen, West Virginia University, Morgantown, WV, U.S.A., Erik Friese, University of Rostock, Germany, and T. Karthick, Computer Science Unit, Indian Statistical Institute, Chennai, India.)
Primary author
Prof.
Andreas Brandstädt
(University of Rostock)
