7
$\begingroup$

Note: Originally, this question was asked via a comment in this question, but was asked to post a separate question. :)

I'm looking for any known reductions of the following: Given a parameterized problem X (whose parameter is not the size of a solution and the size of a solution can still be quite large) showing X is W[t]-complete for some fixed t>=1 (e.g., W[1]-complete, W[2]-complete, but not in FPT).

I'm curious how one can show that X is in W[1] or W[2], e.g., when the size of a solution can still be "n" yet we can only choose "k" input gates as it seems impossible (how could you encode a large solution using only a (fixed) number of bits?). Even though X is known to be W[1]-hard or W[2]-hard, it may actually require circuits with large wefts than 2, for instance, if completeness is not known yet. (Or, perhaps such hardness as X cannot belong to W[t] for any fix t under (some conditions when the solution size is clearly not bounded by the parameter) may be implied in some cases, but I couldn't find any such results, either.)

Here are some problems that do not qualify:

  • The independent set problem parameterized by tree width would be in FPT (although the solution size is not necessarily bounded by the parameter), so it won't qualify.
  • The clique problem parameterized by maximum degree of a vertex would also be in FPT (and in this case, the solution size would be bounded by the parameter anyway), so it won't qualify.
  • The vertex coloring problem (k-coloring) also won't qualify because it's para-NP-hard (i.e., it's not W[t] complete for any fixed constant, t), although its solution size is not bounded by the parameter k.

Update with details (Nov 13):

I now have a concrete problem that (I think) is W[2]-hard and in W[P], but: (1) I can't prove that this is in W[2] (so as to prove that it's W[2]-complete) and (2) I also can't prove that this is W[3]-hard.

We are given n items and m bags (and some constraints to be specified), and we want to assign every item to some bag (subject to constraints below) but only using up to k bags (here, 'k' is the parameter). Constraints are specified per item and bag pair: For each item i and bag j, we are given two numbers L(i, j) and U(i, j) (lower-bound and upper-bound) in [1, n] such that if we assign item i to bag j, then the total number of items assigned to bag j must be between L(i, j) and U(i, j), inclusive. This must be satisfied for all items i in a solution. (L(i, j) > U(i, j) naturally implies that item i can't possibly be assigned to bag j.)

The input consists of O(nm) numbers (two numbers per pair), and a natural solution would be of size O(n): For each item, we describe an index of the bag to which it is assigned. On the other hand, a shorter certificate of size k also makes sense: We can describe which k bags we use in a solution and how many items we assign to each of the said k bags.

To show that this problem is in W[P] (using the shorter certificate):

We need 2k numbers as a certificate: k numbers for the bags used (their indices, log m bits each) and another k numbers for how many items are assigned to each bag (log n bits each). We can non-deterministically guess these 2k numbers, and then solve a max-flow problem (or a bipartite matching problem) in poly-time.

To show that this problem is W[2]-hard: We can reduce from the dominating set problem in a straightforward manner. For each vertex, we create one item and one bag (so n = m in this reduction). For each vertex j and its neighbors i, we set L(i, j) = 1 and U(i, j) = n (this means we can assign item i to bag j). For all other (i, j) pairs (i.e., no edges), we set L(i, j) > U(i, j) (so we can't assign i to j). Clearly, we have a dom-set of size k if and only if we can assign n items to k bags.

The natural description of a solution (of size O(n)) is too large for me to reduce this problem to WCSAT where I can only set O(f(k)) input gates to true. On the other hand, a shorter certificate (that I used above) makes it too difficult to verify (the best I got is W[P] membership above). I realize that perhaps there are other, smarter "short" certificates of size O(f(k)), and that is why I asked the question (to seek other problems/reductions for reference). I haven't been lucky enough to find useful references yet...

$\endgroup$
3
+50
$\begingroup$

The answer to this question depends very much on the definition of what a solution is. Take for example the Vertex Cover problem where we ask whether a graph $G$ has a vertex set $S$ of size at most $k$ such that every edge has an endpoint in $S$. The natural definition of solution size is $k$, the size of the vertex cover.

If you consider the dual parameter $\ell:n-k$ for Vertex Cover, then the problem is W[1]-complete since it is exactly the Independent Set problem. Using a strict definition of what a solution is, this gives an example of a problem that is W[1]-complete for a parameter that is not the solution size.

Now, we may define solution more loosely as some kind of certificate that can be verified efficiently. In that case, any parameterized problem that is in W[1] can be considered to be "parameterized by the solution size": Take for example the characterization of W[1] due to Chen and Flum 1. This characterization states that a problem is in W[1] if it can be solved via a nondeterministic RAM that makes all its nondeterministic guesses in the last $h(k)$ computation steps for some function $h$. It is clear from this definition that a problem in W[1] has a certficate and thus also a solution in the broad sense of size $h(k)$.

So in short: It depends on what one views as a solution. If one takes a very strict view, then it is easy to come up with examples that are W[1]-complete for non-solution size parameters. If one takes a broad view of what a solution is, then a problem that is in W[1] for some parameter $k$ has, by definition, solutions (certificates) of size bounded in $k$.

Yijia Chen, Jörg Flum, Martin Grohe: Machine-based methods in parameterized complexity theory. Theor. Comput. Sci. 339(2-3): 167-199 (2005)

$\endgroup$
3
  • $\begingroup$ Thanks for the first answer! After reading your answer, I think I can better explain exactly what I am after using a specific problem and the issues I ran into. I just added the details to the original post as it would exceed the character limit of a comment... $\endgroup$ Nov 13 '20 at 9:46
  • $\begingroup$ I like the new part of the question but isn't this a new question? It asks for a concrete problem whether one can show containment in W[2] or hardness for W[3]. This differs a a bit from the original question. $\endgroup$ Nov 13 '20 at 10:50
  • $\begingroup$ Yes, I can ask about it as a new question, but I also wanted to related it to my original question; specifically this part: "I'm curious how one can show that X is in W[1] or W[2], e.g., when the size of a solution can still be "n" yet we can only choose "k" input gates as it seems impossible (how could you encode a large solution using only a (fixed) number of bits?). Even though X is known to be W[1]-hard or W[2]-hard, it may actually require circuits with large wefts than 2, for instance, if completeness is not known yet." The concrete question fits this, doesn't it? $\endgroup$ Nov 13 '20 at 12:28

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.