16

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

Jan Johannsen
  • 4,630
  • 2
  • 33
  • 50

2 Answers2

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]

Yixin Cao
  • 2,560
  • 1
  • 16
  • 29
  • 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 07: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 02: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 09:54
14

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

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127