When Is Weighted Satisfiability FPT?

摘要

The weighted monotone and antimonotone satisfiability problems on normalized circuits, abbreviated wsat~+[t] and wsat~-[t], are canonical problems in the parameterized complexity theory. We study the parameterized complexity of wsat~-[t] and wsat~+[t], where t ≥ 2, with respect to the genus of the circuit. For wsat~-[t], we give a fixed-parameter tractable (FPT) algorithm when the genus of the circuit is n~(o(1)), where n is the number of the variables in the circuit. For wsat~+[2] (i.e., weighted monotone cnf-sat) and wsat~+[3], which are both W[2]-complete, we also give FPT algorithms when the genus is n~(o(1)). For wsat~+[t] where t ＞ 3, we give FPT algorithms when the genus is O((log n)~(1/2)). We also show that both wsat~-[t] and wsat~+[t] on circuits of genus n~(Ω(1)) have the same W-hardness as the general wsat~+[t] and wsat~-[t] problem (i.e., with no restriction on the genus), thus drawing a precise map of the parameterized complexity of wsat~-[t], and of wsat~+[t], for t = 2, 3, with respect to the genus of the underlying circuit. As a byproduct of our results, we obtain, via standard parameterized reductions, tight results on the parameterized complexity of several problems with respect to the genus of the underlying graph.