patternMinor
FPT algorithm for edge dominating set
Viewed 0 times
fptedgealgorithmforsetdominating
Problem
I have been attempting to learn parameterized complexity on my own, and decided to go through all of the FPT race problems, and defining easy FPT algorithms for them, using concepts such as bounded search tree. I am stuck on figuring out an FPT algorithm for edge dominating set, defined as follows:
EdgeDominatingSet
Instance: A graph $G=(V,E)$; a positive integer $k$.
Question: Is there a subset $D\subseteq E$ with $|D|\leq k$ such that for each $e\in E$, either $e\in D$ or $e$ shares an endpoint with an $e'\in D$.
Parameter: $k$
I'm not looking to define anything fancy, just a simple FPT result. Any help would be great!
EdgeDominatingSet
Instance: A graph $G=(V,E)$; a positive integer $k$.
Question: Is there a subset $D\subseteq E$ with $|D|\leq k$ such that for each $e\in E$, either $e\in D$ or $e$ shares an endpoint with an $e'\in D$.
Parameter: $k$
I'm not looking to define anything fancy, just a simple FPT result. Any help would be great!
Solution
I'm not sure there are any really simple solutions. One algorithm is due to Fernau, and uses an enumeration of all vertex covers of size $2k$; within each of these, a simple dynamic programming algorithm attempts to find a small edge dominating set. Another (earlier) approach, due to Prieto, uses kernelization.
Context
StackExchange Computer Science Q#23028, answer score: 3
Revisions (0)
No revisions yet.