A Fixed-Parameter Algorithm for Random Instances of Weighted d-CNF Satisfiability

Yong Gao

We study random instances of the weighted $d$-CNF satisfiability problem (WEIGHTED $d$-SAT), a generic W[1]-complete problem. A random instance of the problem consists of a fixed p…