15
$\begingroup$

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

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ 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" :-) :-) $\endgroup$ – Marzio De Biasi Sep 10 '14 at 12:27
  • 2
    $\begingroup$ Well, at least it looks more natural than the defining problems, doesn't it? $\endgroup$ – Jan Johannsen Sep 10 '14 at 13:57
12
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
13
$\begingroup$

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]

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jan Johannsen Sep 19 '14 at 7:36
  • $\begingroup$ 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. $\endgroup$ – Yixin Cao Sep 20 '14 at 2:43
  • $\begingroup$ 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. $\endgroup$ – Jan Johannsen Sep 22 '14 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.