# Simple proof for NP-completeness of Edge Dominating Set

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.

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)