<p>I believe the title of this paper is self-explanatory and answers your question:
<a href="http://dx.doi.org/10.1016/j.tcs.2006.07.016">On product covering in 3-tier supply chain models: Natural complete problems for W[3] and W[4]</a></p>

CC BY-SA 3.0
2014-09-19T07:36:28.900Z
The definition of the problems in that paper are not too easy to read, because the authors don't clearly distinguish between the model and what is being modelled. But a far as I understand them, they are just thinly disguised weighted circuit SAT problems. They may be useful for the application domain, but I doubt that they are any more convenient to reduce from.
Jan Johannsen
CC BY-SA 3.0
2014-09-20T02:43:37.300Z
I partially agree with you on that these problems are not as natural as vertex cover/clique/dominating set etc. But with more and more problems studied but no new candidates emerge, we may have to turn to these sub-natural problems.
Yixin Cao
CC BY-SA 3.0
2014-09-22T09:54:31.323Z
I'm not saying that these problems are not natural. What I'm saying is that they are not very different from the Weighted SAT problems for depth three circuits. As far as I understand, they are more or less the same problem written in a different terminology.
Jan Johannsen
CC BY-SA 3.0
2014-09-11T01:15:54.037Z
2014-09-11T01:15:54.037Z
Yixin Cao
<p>From the comment above:</p>

<p><strong>$p$-HYPERGRAPH-(NON)-DOMINATING-SET</strong> is W[3]-complete under fpt-reductions:</p>

<p>A hypergraph $H = (V,E)$ consists of a set $V$ of vertices and a set $E$ of hyperedges. Each
hyperedge is as subset of $V$. In a 3-hypergraph all edges have size 3. If $H = (V,E)$ is
a 3-hypergraph, every $a \in V$ induces a graph $H^a = (V^a, E^a)$ given by:</p>

<p>$V^a = \{ v \in V \mid v \neq a \text{ and there is } e \in E \text{ with } a, v \in e \}$ and 
$E^a = \{ \{u,v\} \mid \{a,u,v\} \in E \}$</p>

<p><strong>Input</strong>: A 3-hypergraph $H = (V,E)$, a set $M \subseteq V$, and $k \geq 1$.<br>
<strong>Parameter</strong>: $k$.<br>
<strong>Problem</strong>: Decide whether there exists a set $D \subseteq V$ of cardinality $k$ such that:</p>

<ul>
<li>if $a \in M$, then $D$ is a dominating set of $H^a$,</li>
<li>if $a \notin M$, then $D$ is not a dominating set of $H^a$.</li>
</ul>

<p>see <a href="http://www.jstor.org/discover/10.2307/27588555?uid=3738296&amp;uid=2&amp;uid=4&amp;sid=21104617459817" rel="noreferrer">Yijia Chen, Jörg Flum and Martin Grohe. An Analysis of the W*-Hierarchy. The Journal of Symbolic Logic, Vol. 72, No. 2 (Jun., 2007), pp. 513-534</a></p>

CC BY-SA 3.0
2014-09-12T07:51:44.617Z
2014-09-19T08:13:40.257Z
2014-09-19T08:13:40.257Z
Marzio De Biasi
<p>The $\mathsf{W}$-hierarchy is a hierarchy of complexity classes $\mathsf{W}[t]$ in parameterized complexity, see the <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:W#wt">Complexity Zoo</a> for definitions. An alternative definition defines $\mathsf{W}[t]$ using weighted Fagin definability for $\Pi_t$-formulas of first-order logic, see the <a href="http://books.google.de/books/about/Parameterized_Complexity_Theory.html?id=VfJz6hvFAjoC&amp;redir_esc=y">textbook by Flum and Grohe</a>.</p>

<p>For the lowest classes $\mathsf{W}[1]$ and $\mathsf{W}[2]$, many natural complete problems are known, e.g. <em>Clique</em> and <em>Independent Set</em> are complete for $\mathsf{W}[1]$ , and <em>Dominating Set</em> and <em>Hitting Set</em> are complete for $\mathsf{W}[2]$, where each of these problems is defined as the corresponding well-known $\mathsf{NP}$-complete problem with the size of the required solution set as the parameter.   </p>

<p>Are there any known natural complete problems for classes higher up in the $\mathsf{W}$-hierarchy, in particular for $\mathsf{W}[3]$ and $\mathsf{W}[4]$?</p>

CC BY-SA 3.0
2014-09-10T12:27:32.767Z
In [this paper](http://www.jstor.org/discover/10.2307/27588555?uid=3738296&uid=2129&uid=2&uid=70&uid=4&sid=21104672989533) it is proved that p-HYPERGRAPH-(NON)-DOMINATING-SET is W[3]-complete under fpt-reductions  ... but I think that it's difficult to consider it "natural" :-) :-)
Marzio De Biasi
CC BY-SA 3.0
2014-09-10T13:57:24.937Z
Well, at least it looks more natural than the defining problems, doesn't it?
Jan Johannsen
<cc.complexity-theory><parameterized-complexity>
Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy
Jan Johannsen
# Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy

(Asked by: username_0 on 2014-09-10)

The $\mathsf{W}$-hierarchy is a hierarchy of complexity classes $\mathsf{W}[t]$ in parameterized complexity, see the [Complexity Zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:W#wt) for definitions. An alternative definition defines $\mathsf{W}[t]$ using weighted Fagin definability for $\Pi\_t$-formulas of first-order logic, see the [textbook by Flum and Grohe](http://books.google.de/books/about/Parameterized_Complexity_Theory.html?id=VfJz6hvFAjoC&redir_esc=y).

For the lowest classes $\mathsf{W}[1]$ and $\mathsf{W}[2]$, many natural complete problems are known, e.g. *Clique* and *Independent Set* are complete for $\mathsf{W}[1]$ , and *Dominating Set* and *Hitting Set* are complete for $\mathsf{W}[2]$, where each of these problems is defined as the corresponding well-known $\mathsf{NP}$-complete problem with the size of the required solution set as the parameter.

Are there any known natural complete problems for classes higher up in the $\mathsf{W}$-hierarchy, in particular for $\mathsf{W}[3]$ and $\mathsf{W}[4]$?

**Tags:** cc.complexity-theory, parameterized-complexity

> **Comments:**
> **username_1**: In [this paper](http://www.jstor.org/discover/10.2307/27588555?uid=3738296&uid=2129&uid=2&uid=70&uid=4&sid=21104672989533) it is proved that p-HYPERGRAPH-(NON)-DOMINATING-SET is W[3]-complete under fpt-reductions  ... but I think that it's difficult to consider it "natural" :-) :-)  
> **username_0**: Well, at least it looks more natural than the defining problems, doesn't it?  

---

## 2 answers

### Answer by username_1 on 2014-09-12. Score: 14 | Accepted answer

From the comment above:

**$p$-HYPERGRAPH-(NON)-DOMINATING-SET** is W[3]-complete under fpt-reductions:

A hypergraph $H = (V,E)$ consists of a set $V$ of vertices and a set $E$ of hyperedges. Each
hyperedge is as subset of $V$. In a 3-hypergraph all edges have size 3. If $H = (V,E)$ is
a 3-hypergraph, every $a \in V$ induces a graph $H^a = (V^a, E^a)$ given by:

$V^a = \{ v \in V \mid v \neq a \text{ and there is } e \in E \text{ with } a, v \in e \}$ and
$E^a = \{ \{u,v\} \mid \{a,u,v\} \in E \}$

**Input**: A 3-hypergraph $H = (V,E)$, a set $M \subseteq V$, and $k \geq 1$.  
**Parameter**: $k$.  
**Problem**: Decide whether there exists a set $D \subseteq V$ of cardinality $k$ such that:

* if $a \in M$, then $D$ is a dominating set of $H^a$,
* if $a \notin M$, then $D$ is not a dominating set of $H^a$.

see [Yijia Chen, Jörg Flum and Martin Grohe. An Analysis of the W\*-Hierarchy. The Journal of Symbolic Logic, Vol. 72, No. 2 (Jun., 2007), pp. 513-534](http://www.jstor.org/discover/10.2307/27588555?uid=3738296&uid=2&uid=4&sid=21104617459817)


---

### Answer by username_2 on 2014-09-11. Score: 15

I believe the title of this paper is self-explanatory and answers your question:
[On product covering in 3-tier supply chain models: Natural complete problems for W[3] and W[4]](http://dx.doi.org/10.1016/j.tcs.2006.07.016)

> **Comments:**
> **username_0**: The definition of the problems in that paper are not too easy to read, because the authors don't clearly distinguish between the model and what is being modelled. But a far as I understand them, they are just thinly disguised weighted circuit SAT problems. They may be useful for the application domain, but I doubt that they are any more convenient to reduce from.  
> **username_2**: I partially agree with you on that these problems are not as natural as vertex cover/clique/dominating set etc. But with more and more problems studied but no new candidates emerge, we may have to turn to these sub-natural problems.  
> **username_0**: I'm not saying that these problems are not natural. What I'm saying is that they are not very different from the Weighted SAT problems for depth three circuits. As far as I understand, they are more or less the same problem written in a different terminology.  

---

