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-complete, W-complete, but not in FPT).
I'm curious how one can show that X is in W or W, 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-hard or W-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-hard and in W[P], but: (1) I can't prove that this is in W (so as to prove that it's W-complete) and (2) I also can't prove that this is W-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
such that if we assign item
i to bag
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
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
To show that this problem is in
W[P] (using the shorter certificate):
2k numbers as a certificate:
k numbers for the bags used (their indices,
log m bits each)
k numbers for how many items are assigned to each bag (
log n bits each). We can non-deterministically guess these
and then solve a max-flow problem (or a bipartite matching problem) in poly-time.
To show that this problem is
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
L(i, j) = 1 and
U(i, j) = n (this means we can assign item
i to bag
For all other
(i, j) pairs (i.e., no edges), we set
L(i, j) > U(i, j) (so we can't assign
Clearly, we have a dom-set of size
k if and only if we can assign
n items to
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...