License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.91
URN: urn:nbn:de:0030-drops-164323
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16432/
Lokshtanov, Daniel ;
Panolan, Fahad ;
Ramanujan, M. S.
Backdoor Sets on Nowhere Dense SAT
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.
BibTeX - Entry
@InProceedings{lokshtanov_et_al:LIPIcs.ICALP.2022.91,
author = {Lokshtanov, Daniel and Panolan, Fahad and Ramanujan, M. S.},
title = {{Backdoor Sets on Nowhere Dense SAT}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {91:1--91:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16432},
URN = {urn:nbn:de:0030-drops-164323},
doi = {10.4230/LIPIcs.ICALP.2022.91},
annote = {Keywords: Fixed-parameter Tractability, Satisfiability, Backdoors, Treewidth}
}
|
Keywords: |
|
Fixed-parameter Tractability, Satisfiability, Backdoors, Treewidth |
|
Collection: |
|
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
28.06.2022 |
