7
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.