← 研踪 PaperTrailarXiv:2611.12321 · v1
Strong Backdoor to Forests is FPT: Tight Linear-Time FPT for Essentially General SAT
首次提交 2026-11-09 20:43
版本更新 2026-11-09 20:43
雷达观测 2026-11-10 15:22
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-09 20:43 · 最新观测版本
Strong Backdoor to Forests is FPT: Tight Linear-Time FPT for Essentially General SAT
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.
查看此版本解读 →查看此版本原文 ↗