Simple proof for NP-completeness of Edge Dominating Set

Question

In a graph, an edge dominating set is a subset D of the edges such that any edge in the graph is either in D, or shares an endpoint with an edge in D. The Minimum Edge Dominating Set problem is to find an edge dominating set of minimum cardinality. The decision version of this problem is known to be NP-complete, but I would like to inquire whether a relatively simple proof of this fact is known.

The only proof I found in the literature is in the paper that first tackled this problem, by Gavril and Yannakakis. However, the above proof makes use of the fact that Vertex Cover is NP-complete for planar cubic graphs, and the fact that bipartite graphs of degree d can be d-edge-colored. I would prefer a simpler proof, that would only make use of facts typically known to undergraduates who took an algorithms course.

Answer 1

I assume that you only want to show the minimum edge dominating set problem is NP-complete for the general graph (i.e., you don't care about what properties the constructed graph has).

In case you missed it, there is an arguably simpler reduction from 3-SAT in the same paper (see Theorem 2). The reduction assumes no further "specialist" knowledge. You can make the presentation even slightly easier by skipping verification of bipartiteness and boundedness of the maximum degree of the resulting graph.

Answer 2

There is a simple reduction in paper Approximation hardness of edge dominating set problems (Chlebík and Chlebíková, Journal of Combinatorial Optimization 11(3):279–290, 2006).

The reduction is add a universal vertex connected to all nodes and replace every edge by a $P_5$ with a pendent edge added to the middle vertex. There is an edge dominating set of size $|E|+k$ in the new graph iff there is a vertex cover of size $k$ in the original one. You will need at least one edge for each gadget; the rest is classical. (Actually I think you don't need the universal vertex)

Answer 3

We will reduce Vertex Cover to Edge Dominating Set and complete the proof. Given an instance of the decision version of vertex cover problem $I(G,k)$, we construct $G'$ by adding $nk+k$ new edges to $G$, where $n$ is the number of vertices in $G$:

• add $k$ new vertices;
• add an edge between each of these new vertices and each vertex in $G$, totally $nk$ edges, called intermediate edges;
• add a pendant edge to each of the new vertices, totally $k$ edges.

Observe that the edge dominating set in $G'$ contains at least $k$ edges. Also observe that any edge domindating set of size $k$ in $G'$ can only contain intermediate edges. Then we claim that $G$ has a vertex cover of size $k$ iff $G'$ has an edge dominating set of size $k$.