Packing and covering problems in graphs and hypergraphs and their relationships belong to the most fundamental topics in combinatorics and graph algorithms and have a wide spectrum of applications in computer science, operations research and many other fields. Vertex Cover is a typical example of a covering problem, and Maximum Independent Set is a typical example of a packing problem, and the complexity of these two problems was investigated in thousands of papers.
Recently, there has been an increasing interest in problems combining packing and covering properties. For a hypergraph H = (V, E), Exact Cover is a classical problem asking for the existence of a subcollection E′ ⊆ E such that every vertex of V is contained in exactly one hyperedge from E′. It is well known that this problem is NP- complete even when the hyperedges contain only three vertices called Exact Cover by 3-Sets.
Among the problems combining packing and covering properties, there are the follo- wing variants of domination problems: Let G = (V, E) be a finite undirected and simple graph, and let N(G) denote the closed neighborhood hypergraph of G. A vertex set U ⊆ V is an efficient dominating set in G if the closed neighborhoods of vertices in U form an exact cover in N (G). An edge set M ⊆ E is an efficient edge dominating set in G if M is an efficient dominating set in the line graph L(G). Note that not every graph has an efficient dominating set (an efficient edge dominating set, respectively). The problem Efficient Domination (Efficient Edge Domination, respective- ly) asks for the existence of such a vertex set (edge set, respectively). It is well known that both problems are NP-complete, even for bipartite graphs. We give some new ca- ses where the problems are efficiently solvable by using structural properties of graph classes and using closure properties under the square operation, and we also generalize the problems to hypergraphs.
