patternMinor
Simple proof for NP-completeness of Edge Dominating Set
Viewed 0 times
simpleedgecompletenessforsetproofdominating
Problem
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 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.
Solution
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.
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.
Context
StackExchange Computer Science Q#67647, answer score: 5
Revisions (0)
No revisions yet.