Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy

The $\mathsf{W}$-hierarchy is a hierarchy of complexity classes $\mathsf{W}[t]$ in parameterized complexity, see the Complexity Zoo 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.

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]$?

• In this paper 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 Sep 10 '14 at 12:27
• Well, at least it looks more natural than the defining problems, doesn't it? – Jan Johannsen Sep 10 '14 at 13:57

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$.

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]

• 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 Sep 19 '14 at 7:36
• 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 Sep 20 '14 at 2:43
• 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 Sep 22 '14 at 9:54