2
$\begingroup$

By "complement problems", I mean the two problems' objective functions are complement. For example, the vertex cover and its complement independent set in this sense. For a graph $G(V,E)$, their answers add up to $|V|$. Another example is a problem I am working on. The dominating set problem and its complement "packing as many edges as possible so that there is no path or circle whose length is more than 2". Dominating set is $W[2]$-complete in the sense, and the edge packing problem is in $W[1]$-complete( whether it is complete in $W[1]$, I am still looking).

So, I come to the following audacious conjecture. If problem A and problem B are complement, then A and B are not in the same class in the parameterized complexity structure, i.e. $FPT \subseteq W[1] \subseteq W[2] \subseteq \cdots W[SAT] $. Of course, there is another condition : A and B are not $P$ in the classical complexity hierarchy.

I am not very familiar with parameterized complexity theory. So, any advice is welcome. Thank you very much.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ I have two questions. (1) I wonder why your edge packing problem is the complement of the dominating set problem. One is an edge problem and the other is a vertex problem. (2) In your conjecture, do you assume some complexity-theoretic separation? It's possible that FPT = W[1], and so on. So, your conjecture only makes sense with some assumption. $\endgroup$ – Yoshio Okamoto Jan 4 '12 at 10:06
  • $\begingroup$ @YoshioOkamoto Thank you very much for your comment. (1) There is a $k$ sized dominating set if and only if there is a valid packing with $|V|-k$ edges. I call its complement in the sense that their solution size complement each other. (2). Yes, I assume the hierarchy is strict. $\endgroup$ – Peng Zhang Jan 4 '12 at 12:36
9
$\begingroup$

The complement problems Minimum (Edge) Bipartization and MaxCut are both in FPT, so the conjecture is false.

|cite|improve this answer
$\endgroup$
  • 5
    $\begingroup$ Another class of examples can be found when looking at planar graphs: Independent Set and Vertex Cover are both NP-complete and FPT on planar graphs; the same for Dominating Set/Non-Blocker, Connected Dominating Set/Max Leaf, and so on. $\endgroup$ – Bart Jansen Jan 4 '12 at 11:20
  • 1
    $\begingroup$ Moreover, one could be rather silly and define a P-time solvable problem on a graph that involves computing some subset. The complement is also in P. therefore both are in FPT. $\endgroup$ – Suresh Venkat Jan 5 '12 at 6:25

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.