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

$\endgroup$
2
  • 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$ Commented Sep 10, 2014 at 12:27
  • 2
    $\begingroup$ Well, at least it looks more natural than the defining problems, doesn't it? $\endgroup$ Commented Sep 10, 2014 at 13:57

2 Answers 2

14
$\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

$\endgroup$
0
15
$\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]

$\endgroup$
3
  • $\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$ Commented Sep 19, 2014 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
    Commented Sep 20, 2014 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$ Commented Sep 22, 2014 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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