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

CC BY-SA 3.0
2012-01-04T11:20:51.113Z
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.
Bart Jansen
CC BY-SA 3.0
2012-01-05T06:25:26.457Z
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.
Suresh Venkat
CC BY-SA 3.0
2012-01-04T10:22:07.113Z
2012-01-04T10:22:07.113Z
Falk Hüffner
<p>By "<em>complement problems</em>", 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 <em>edge packing</em> problem is in $W[1]$-complete( whether it is complete in $W[1]$, I am still looking). </p>

<p>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.</p>

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

CC BY-SA 3.0
2012-01-04T10:06:16.623Z
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.
Yoshio Okamoto
CC BY-SA 3.0
2012-01-04T12:36:22.840Z
@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.
Peng Zhang
<parameterized-complexity><fixed-parameter-tractable>
Complement problems are not in the same class in parametrized complexity hierarchy? If not in $P$
Peng Zhang
# Complement problems are not in the same class in parametrized complexity hierarchy? If not in $P$

(Asked by: username_0 on 2012-01-04)

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.

**Tags:** parameterized-complexity, fixed-parameter-tractable

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2012-01-04. Score: 10 | Accepted answer

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

> **Comments:**
> **username_3**: 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.  
> **username_4**: 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.  

---

