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

Simple item page
dc.creatorGao, Yong
dc.date2008-06-28
dc.date.accessioned2026-07-07T12:19:43Z
dc.date.available2026-07-07T12:19:43Z
dc.descriptionWe 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 parameter $k$ and a random $d$-CNF formula $\weicnf{n}{p}{k, d}$ generated as follows: for each subset of $d$ variables and with probability $p$, a clause over the $d$ variables is selected uniformly at random from among the $2^d - 1$ clauses that contain at least one negated literals. We show that random instances of WEIGHTED $d$-SAT can be solved in $O(k^2n + n^{O(1)})$-time with high probability, indicating that typical instances of WEIGHTED $d$-SAT under this instance distribution are fixed-parameter tractable. The result also hold for random instances from the model $\weicnf{n}{p}{k,d}(d')$ where clauses containing less than $d' (1 < d' < d)$ negated literals are forbidden, and for random instances of the renormalized (miniaturized) version of WEIGHTED $d$-SAT in certain range of the random model's parameter $p(n)$. This, together with our previous results on the threshold behavior and the resolution complexity of unsatisfiable instances of $\weicnf{n}{p}{k, d}$, provides an almost complete characterization of the typical-case behavior of random instances of WEIGHTED $d$-SAT.
dc.description13 pages
dc.identifierhttps://arxiv.org/abs/0806.4652
dc.identifierhttp://arxiv.org/abs/0806.4652
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/212855
dc.subjectData Structures and Algorithms
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.titleA Fixed-Parameter Algorithm for Random Instances of Weighted d-CNF Satisfiability
dc.typetext

Files

Collections

arXiv