The Library
Backdoors to nowhere dense SAT
Tools
Lokshtanov, Daniel, Panolan, Fahad and Ramanujan, Maadapuzhi Sridharan (2022) Backdoors to nowhere dense SAT. In: 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP), Paris, France ; Virtual, 4-8 Jul 2022. Published in: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), 229 91:1-91:20. ISBN 9783959772358. doi:10.4230/LIPIcs.ICALP.2022.91 ISSN 1868-8969.
|
PDF
WRAP-backdoors-nowhere-dense-SAT-Ramanujan-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (888Kb) | Preview |
|
PDF
WRAP-backdoors-nowhere-dense-SAT-Ramanujan-2022.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (634Kb) |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.91
Abstract
For a satisfiable CNF formula ϕ and an integer t, a weak backdoor set to treewidth-t is a set of variables such that there is an assignment to this set that reduces ϕ to a satisfiable formula that has an incidence graph of treewidth at most t. A natural research program in the work on fixed-parameter algorithms (FPT algorithms) for SAT is to delineate the tractability borders for the problem of detecting a small weak backdoor set to treewidth-t formulas. In this line of research, Gaspers and Szeider (ICALP 2012) showed that detecting a weak backdoor set of size at most k to treewidth-1 is W[2]-hard parameterized by k if the input is an arbitrary CNF formula. Fomin, Lokshtanov, Misra, Ramanujan and Saurabh (SODA 2015), showed that if the input is d-CNF, then detecting a weak backdoor set of size at most k to treewidth-t is fixed-parameter tractable (parameterized by k,t,d). These two results indicate that sparsity of the input plays a role in determining the parameterized complexity of detecting weak backdoor sets to treewidth-t.
In this work, we take a major step towards characterizing the precise impact of sparsity on the parameterized complexity of this problem by obtaining algorithmic results for detecting small weak backdoor sets to treewidth-t for input formulas whose incidence graphs belong to a nowhere-dense graph class. Nowhere density provides a robust and well-understood notion of sparsity that is at the heart of several advances on model checking and structural graph theory. Moreover, nowhere-dense graph classes contain many well-studied graph classes such as bounded treewidth graphs, graphs that exclude a fixed (topological) minor and graphs of bounded expansion.
Our main contribution is an algorithm that, given a formula ϕ whose incidence graph belongs to a fixed nowhere-dense graph class and an integer k, in time f(t,k)|ϕ|^O(1), either finds a satisfying assignment of ϕ, or concludes correctly that ϕ has no weak backdoor set of size at most k to treewidth-t.
To obtain this algorithm, we develop a strategy that only relies on the fact that nowhere-dense graph classes are biclique-free. That is, for every nowhere-dense graph class, there is a p such that it is contained in the class of graphs that exclude K_{p,p} as a subgraph. This is a significant feature of our techniques since the class of biclique-free graphs also generalizes the class of graphs of bounded degeneracy, which are incomparable with nowhere-dense graph classes. As a result, our algorithm also generalizes the results of Fomin, Lokshtanov, Misra, Ramanujan and Saurabh (SODA 2015) for the special case of d-CNF formulas as input when d is fixed. This is because the incidence graphs of such formulas exclude K_{d+1,d+1} as a subgraph.
Item Type: | Conference Item (Paper) | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Computer algorithms, Combinatorial analysis, Parameter estimation, Machine theory, Computer science -- Mathematics | ||||||||||||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||||||||||||||
Journal or Publication Title: | 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) | ||||||||||||||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||||||||||||||
ISBN: | 9783959772358 | ||||||||||||||||||
ISSN: | 1868-8969 | ||||||||||||||||||
Official Date: | 28 June 2022 | ||||||||||||||||||
Dates: |
|
||||||||||||||||||
Volume: | 229 | ||||||||||||||||||
Page Range: | 91:1-91:20 | ||||||||||||||||||
DOI: | 10.4230/LIPIcs.ICALP.2022.91 | ||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||||||||
Date of first compliant deposit: | 27 April 2022 | ||||||||||||||||||
Date of first compliant Open Access: | 22 July 2022 | ||||||||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||||||||
Conference Paper Type: | Paper | ||||||||||||||||||
Title of Event: | 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP) | ||||||||||||||||||
Type of Event: | Conference | ||||||||||||||||||
Location of Event: | Paris, France ; Virtual | ||||||||||||||||||
Date(s) of Event: | 4-8 Jul 2022 | ||||||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year