pipette
ESEspañol

Strong Backdoor to Forests is FPT: Tight Linear-Time FPT for Essentially General SAT

Olesia Bilyk, Aidar Munduzbaev, Roohani Sharma, Mamnoon Siam

Preprint

In the authors' words

In a seminal work, Gaspers and Szeider [FOCS 2013] gave a fixed-parameter tractable (FPT) approximate algorithm for finding a strong backdoor of size at most to incidence treewidth at most , for a given CNF-formula . In particular, their algorithm runs in time, and finds a strong backdoor to treewidth at most , of , of size at most whenever there exists one of size at most . Determining whether the detection of strong backdoors to bounded incidence treewidth is FPT parameterized by was left open in their work and this has been repeatedly posed as an open question by Gaspers and Szeider, for example in [The Multivariate Algorithmic Revolution and Beyond 2012] and more recently in [Computer Science Reviews 2025], even for incidence forests and when the input is a -CNF formula. We answer this question affirmatively. We show that strong backdoors to forests can be found in linear-FPT time on arbitrary non-tautological CNF formulas (not just on 3-CNF formulas). Given such a formula and a budget , our algorithm finds a strong backdoor to the class of forests, of size at most , or correctly reports that none exists, in time. Moreover, we show that our result is as tight as it can get. First, we show that finding strong backdoors to treewidth for any is W[1]-hard, even on non-tautological 3-CNF formulas. Second, the running time of our algorithm is tight: it is linear in the input size and a better than double-exponential dependence on in the running time would imply a -time algorithm for solving 3-SAT on variables, which would beat even the very recently claimed sub-exponential algorithm for solving 3-SAT by OpenAI and Anthropic.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.