3
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • $\begingroup$ I tried to see if any combinatorial techniques I could think of would work, or bounded search tree algorithms, but I cannot find anything to bound by the parameter k $\endgroup$
    – user16086
    Mar 25, 2014 at 12:46
  • $\begingroup$ What's an "FPT race problem"? $\endgroup$
    – David Richerby
    Mar 25, 2014 at 13:56
  • $\begingroup$ fpt.wikidot.com/fpt-races $\endgroup$
    – user16086
    Mar 25, 2014 at 14:09

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! I was just looking for something a bit simpler, but yeah the parameter k doesn't give you much to work with $\endgroup$
    – user16086
    Mar 25, 2014 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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