Skip to main content

Research Repository

Advanced Search

On the parameterized complexity of (k,s)-SAT

Paulusma, D.; Szeider, S.

On the parameterized complexity of (k,s)-SAT Thumbnail


Authors

S. Szeider



Abstract

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 ≥ 3 and s ≥ k, an FPT algorithm for (k, s)-SAT when parameterized by the number t of variables occurring in more than k clauses.

Citation

Paulusma, D., & Szeider, S. (2019). On the parameterized complexity of (k,s)-SAT. Information Processing Letters, 43, 34-36. https://doi.org/10.1016/j.ipl.2018.11.005

Journal Article Type Article
Acceptance Date Nov 13, 2018
Online Publication Date Nov 16, 2018
Publication Date Mar 31, 2019
Deposit Date Nov 28, 2018
Publicly Available Date Nov 16, 2019
Journal Information Processing Letters
Print ISSN 0020-0190
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 43
Pages 34-36
DOI https://doi.org/10.1016/j.ipl.2018.11.005
Public URL https://durham-repository.worktribe.com/output/1308403

Files





You might also like



Downloadable Citations