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...
