Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

Paulusma, D. and Szeider, S. (2019) 'On the parameterized complexity of (k,s)-SAT.', Information processing letters., 43 . pp. 34-36.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(363Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.ipl.2018.11.005
Publisher statement:© 2018 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:13 November 2018
Date deposited:29 November 2018
Date of first online publication:16 November 2018
Date first made open access:16 November 2019

Save or Share this output

Export:
Export
Look up in GoogleScholar