[Back]

D. Paulusma, S. Szeider:
"On the parameterized complexity of (k, s)-SAT";
Information Processing Letters, 134 (2019), 134; 34 - 36.

Let (k, s)-SAT be the k-SAT problem restricted to formulas in which each variable occurs in at most s clauses. It is well known that (3, 3)-SAT is trivial and (3, 4)-SAT is NP-complete. Answering a question posed by Iwama and Takaki (DMTCS 1997), Berman, Karpinski and Scott (DAM 2007) gave, for every fixed t≥0, a polynomial-time algorithm for (3, 4)-SAT restricted to formulas in which the number of variables that occur in four clauses is t. Parameterized by t, their algorithm runs in XP time. We extend their result by giving, for every k ≥3and s ≥k, an FPT algorithm for(k, s)-SAT when parameterized by the number t of variables occurring in more than k clauses.

http://dx.doi.org/10.1016/j.ipl.2018.11.005

https://publik.tuwien.ac.at/files/publik_282806.pdf