2011/12/05 by Iyad Kanj, Kanj, Iyad, Ge Xia +1
Computer Science · #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Formal Methods in Verification #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.1112.1040
openalex publication_date 2011/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the weighted antimonotone and the weighted monotone satisfiability problems on normalized circuits of depth at most t ≥ 2, abbreviated \sc wsat-[t] and \sc wsat+[t], respectively. These problems model the weighted satisfiability of antimonotone and monotone propositional formulas (including weighted anitmonoone/monotone \sc cnf-sat) in a natural way, and serve as the canonical problems in the definition of the parameterized complexity hierarchy. We characterize the parameterized complexity of \sc wsat-[t] and \sc wsat+[t] with respect to the genus of the circuit. For \sc wsat-[t], which is W[t]-complete for odd t and W[t-1]-complete for even t, the characterization is precise: We show that \sc wsat-[t] is fixed-parameter tractable (FPT) if the genus of the circuit is no(1) (n is the number of the variables in the circuit), and that it has the same W-hardness as the general \sc wsat-[t] problem (i.e., with no restriction on the genus) if the genus is nO(1). For \sc wsat+[2] (i.e., weighted monotone \sc cnf-sat), which is W[2]-complete, the characterization is also precise: We show that \sc wsat+[2] is FPT if the genus is no(1) and W[2]-complete if the genus is nO(1). For \sc wsat+[t] where t > 2, which is W[t]-complete for even t and W[t-1]-complete for odd t, we show that it is FPT if the genus is O(√logn), and that it has the same W-hardness as the general \sc wsat+[t] problem if the genus is nO(1).