跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 kk to incidence treewidth at most tt, for a given CNF-formula φφ. In particular, their algorithm runs in f(k,t)∣φ∣3f(k,t) |φ|^3 time, and finds a strong backdoor to treewidth at most tt, of φφ, of size at most 2k2^k whenever there exists one of size at most kk. Determining whether the detection of strong backdoors to bounded incidence treewidth is FPT parameterized by k+tk+t 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 33-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 kk, our algorithm finds a strong backdoor to the class of forests, of size at most kk, or correctly reports that none exists, in 22O(k)∣φ∣2^{2^{O(k)}} |φ| time. Moreover, we show that our result is as tight as it can get. First, we show that finding strong backdoors to treewidth tt for any t≥2t \geq 2 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 kk in the running time would imply a 2o(N/log⁡N)2^{o(N/\log N)}-time algorithm for solving 3-SAT on NN variables, which would beat even the very recently claimed sub-exponential algorithm for solving 3-SAT by OpenAI and Anthropic.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 kk to incidence treewidth at most tt, for a given CNF-formula φφ. In particular, their algorithm runs in f(k,t)∣φ∣3f(k,t) |φ|^3 time, and finds a strong backdoor to treewidth at most tt, of φφ, of size at most 2k2^k whenever there exists one of size at most kk. Determining whether the detection of strong backdoors to bounded incidence treewidth is FPT parameterized by k+tk+t 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 33-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 kk, our algorithm finds a strong backdoor to the class of forests, of size at most kk, or correctly reports that none exists, in 22O(k)∣φ∣2^{2^{O(k)}} |φ| time. Moreover, we show that our result is as tight as it can get. First, we show that finding strong backdoors to treewidth tt for any t≥2t \geq 2 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 kk in the running time would imply a 2o(N/log⁡N)2^{o(N/\log N)}-time algorithm for solving 3-SAT on NN variables, which would beat even the very recently claimed sub-exponential algorithm for solving 3-SAT by OpenAI and Anthropic.

查看此版本解读 →查看此版本原文 ↗