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 treewidtht 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 fixedparameter algorithms (FPT algorithms) for SAT is to delineate the tractability borders for the problem of detecting a small weak backdoor set to treewidtht formulas. In this line of research, Gaspers and Szeider (ICALP 2012) showed that detecting a weak backdoor set of size at most k to treewidth1 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 dCNF, then detecting a weak backdoor set of size at most k to treewidtht is fixedparameter 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 treewidtht.
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 treewidtht for input formulas whose incidence graphs belong to a nowheredense graph class. Nowhere density provides a robust and wellunderstood notion of sparsity that is at the heart of several advances on model checking and structural graph theory. Moreover, nowheredense graph classes contain many wellstudied 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 nowheredense 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 treewidtht.
To obtain this algorithm, we develop a strategy that only relies on the fact that nowheredense graph classes are bicliquefree. That is, for every nowheredense 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 bicliquefree graphs also generalizes the class of graphs of bounded degeneracy, which are incomparable with nowheredense 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 dCNF 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:191:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16432},
URN = {urn:nbn:de:0030drops164323},
doi = {10.4230/LIPIcs.ICALP.2022.91},
annote = {Keywords: Fixedparameter Tractability, Satisfiability, Backdoors, Treewidth}
}
28.06.2022
Keywords: 

Fixedparameter Tractability, Satisfiability, Backdoors, Treewidth 
Seminar: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Issue date: 

2022 
Date of publication: 

28.06.2022 