# Complement problems are not in the same class in parametrized complexity hierarchy? If not in $P$

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$-complete in the sense, and the edge packing problem is in $W$-complete( whether it is complete in $W$, 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 \subseteq W \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.

• 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, and so on. So, your conjecture only makes sense with some assumption. Jan 4 '12 at 10:06
• @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. Jan 4 '12 at 12:36