Traditionally, the $W$ hierarchy is defined around the problem of weighted circuit satisfiability. More precisely, the class $W[t]$ is defined as the closure under $\mathrm{fpt}$-reductions of the following problem.

Given a circuit of weft at most $t$, and depth bounded by a constant, decide whether there is a satisfying assignment of weight exactly $k$.

My question is whether it would be equivalent to define it using the same problem but with weight at most k instead.

This seems to be true for even levels, as there is a theorem (Theorem 7.1 in Parameterized Complexity, Flum and Grohe, 2006) stating that for such levels the problem of finding a satisfying assignment of weight exactly $k$, in a monotone circuit, is $W[t]$-complete. On monotone circuits there is a satisfying assignment of weight exactly $k$ iff there is one of weight at most $k$.

The same argument can't be used however on odd levels, but I would be very surprised if the result wasn't true, so I think there might be a simple proof.

Any help would be appreciated.


1 Answer 1


No, but something similar holds true.

There is sort of a duality between even and odd levels of the W hierarchy. In particular, maximization problems like p-IndependentSet tend to inhabit the odd levels while minimization problems like p-DominatingSet inhabit the even levels. Asking for something of weight $\leq k$ is a minimization problem.

In terms of p-WSAT, the result you cite extends as follows: For odd levels, antitone levels suffice (antitone means that all atoms are negated). Then, there is a satisfying assignment of weight $k$ iff there is one of weight $\geq k$ (provided there are $\geq k$ variables at all, but if there aren't, the problem can be solved in FPT time by brute force).

And if you choose the wrong monotonicity, you even drop by one level: If $t$ is odd, then p-WSAT for monotone weft $t$, depth $d$ circuits is complete for $W[t-1]$ (respectively is in FPT for $t=1$). If $t$ is even, the same holds for p-WSAT for antitone such circuits. I'll sktech a partial proof.

Let us stick with odd $t$. Using standard normalizations, we can also assume that the circuit is in fact a tree of depth $t+1$ with alternating layers of AND and OR gates, the tree root being an AND gate, and small gates only in the very last layer. As $t$ is odd, the lowest sub-trees all are in $f$-CNF, where the bound $f$ on clause size is the fan-in bound for small gates from the definition of weft.

For some intuition, let us first assume $f=2$. Then, we have monotone 2-CNFs. Consider the graph whose vertices are variables and whose edges are clauses of the 2-CNF at hand. A satisfying assignment of the 2-CNF is a vertex cover of the graph and vice versa. We know how to handle vertex cover in FPT time.

More precisely, using the bounded branching algorithm for p-VertexCover, we can also do the following in FPT time: List all minimal vertex covers of size $\leq k$ of a given graph. With the same technique we can also solve the respective problem for arbitrary $f$: Given a monotone $f$-CNF circuit, list its minimal satisfying assignments of weight $\leq k$. Then, generate a new circuit with an OR gate at top. It has one input for each minimal satisfying assignment from the list. This input is an AND gate, whose inputs in turn are the variables that are set to true in that assignment. It can be seen that the new $k$-DNF circuit is equivalent to the old $f$-CNF one for assignments of weight $\leq k$. Thus we can replace each $f$-CNF subtree by its respective $k$-DNF subtree. After merging the latter's top OR gate with the OR gate that was the former's parent, we have reduced depth to $t$.

As sketched here, the fan-in of small gates is not bounded by a constant any more but by the parameter. Further techniques can remedy this. For the present purpose however, it may be sufficient that we have seen the depth to collapse by $1$.


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.