CS Paper Radar

Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity

Jan Dreier, Robert Ganian, Marlene Gründel, Roohani Sharma, Simon Wietheger

cs.DS cs.CC ·submitted 2026-10-13 15:20 UTC · v1

Abstract

The Boolean Satisfiability (SAT) problem is a remarkably expressive computational problem, serving both as a cornerstone of complexity theory and as a unifying language for a wide range of search and reasoning tasks. While $\mathrm{NP}$-complete in general, SAT is well known to be linear-time solvable on instances with bounded treewidth. This motivates the search for "hidden" tree-like structures in formulas---for instance by detecting so-called weak $t$-treewidth backdoors. Such backdoors are sets of $k$ variables that can be assigned in such a way that the remaining instance has treewidth at most $t$ and is satisfiable whenever the original instance is. Ever since Gaspers and Szeider [ICALP 2012] showed that finding a weak $t$-treewidth backdoor for a SAT formula is $\mathrm{W}[2]$-hard with respect to $k$, tractability results have been restricted to structurally sparse formulas---most notably, a linear-time algorithm for $d$-SAT (bounded clause-length SAT) by Fomin, Lokshtanov, Misra, Ramanujan, and Saurabh [SODA 2015] and a non-uniform polynomial-time algorithm when the incidence graph of the input formula belongs to a nowhere-dense graph class (or more generally is $K_{d,d}$-free) by Lokshtanov, Panolan, and Ramanujan [ICALP 2022]. In this paper, we push the tractability boundaries of finding weak $t$-treewidth backdoors beyond sparsity and into the regime of "well-behaved" dense formulas. Aiming towards relaxing structural input restrictions from nowhere-dense to edge-stable graph classes, as featured in the theory of beyond sparsity for FO model checking, or to bounded VC-dimension set systems, we identify signed semi-ladder-freeness as the correct dense structural restriction that establishes the boundary between tractability and intractability along this line.

Closest papers

Nearest neighbours by meaning across the whole index.

An Improved Algorithm for Quantified Boolean Formulas

cs.DS cs.AI ·2026-11-07 ·Zhiyang Chen, Hailong Yao
similarity 0.66
Abstract

Quantified Boolean formula (QBF), the quantified version of Boolean satisfiability (SAT), is a fundamental problem in constraint solving. Due to the $\mathsf{PSPACE}$-complete nature of QBF, designing theoretically efficient QBF algorithms is much harder and receives less attention in academia. In this work, we present a new algorithm based on memoized search, which solves QBF with $n$ variables and $m$ clauses in $1.685^m\cdot\text{poly}(n)$ time and space. This is the first improvement over the $1.709^m\cdot\text{poly}(n)$ bound by Williams in over 20 years. Our technique is based on the minimum vertex cover of the conflict graphs, which was proposed to study the parameterized complexity of SAT. We extend this idea to QBF and further show that QBF is slicewise polynomial-time solvable using this parameter.

0.22

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

cs.DS cs.CC ·2026-11-09 ·Olesia Bilyk, Aidar Munduzbaev, Roohani Sharma, Mamnoon Siam
similarity 0.65
Abstract

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 $k$ to incidence treewidth at most $t$, for a given CNF-formula $φ$. In particular, their algorithm runs in $f(k,t) |φ|^3$ time, and finds a strong backdoor to treewidth at most $t$, of $φ$, of size at most $2^k$ whenever there exists one of size at most $k$. Determining whether the detection of strong backdoors to bounded incidence treewidth is FPT parameterized by $k+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 $3$-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 $k$, our algorithm finds a strong backdoor to the class of forests, of size at most $k$, or correctly reports that none exists, in $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 $t$ for any $t \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 $k$ in the running time would imply a $2^{o(N/\log N)}$-time algorithm for solving 3-SAT on $N$ variables, which would beat even the very recently claimed sub-exponential algorithm for solving 3-SAT by OpenAI and Anthropic.

0.17

Robust Approximation and the Arity Barrier at Width Two

cs.CC ·2026-09-29 ·Nathan Benedetto Proença, Koppány István Encz, Monaldo Mastrolilli
theory similarity 0.64
Abstract

Zwick's algorithm for Horn satisfiability shows that constraints of unbounded arity can admit a robust approximation guarantee independent of the arity. For finite constraint languages, Barto and Kozik proved that robust approximability is characterized by bounded width. We ask whether arity-independent robustness persists beyond width one and show that it fails already at width two. For Majority-closed Boolean linear constraints of maximum arity $k \ge 2$, we give a randomized polynomial-time algorithm that, without knowing $\varepsilon$, violates an expected $O(\sqrt{\varepsilon \log k})$ fraction of the constraint weight on $(1-\varepsilon)$-satisfiable instances. Under the Unique Games Conjecture (UGC), a matching NP-hardness lower bound of $Ω(\sqrt{\varepsilon \log k})$ holds in an explicit parameter regime. Under this assumption, the bounded-width characterization therefore does not extend uniformly to constraints of unbounded arity. The algorithm rounds a degree-eight Sum-of-Squares (SoS) relaxation with a single Gaussian threshold. Since polynomial size alone does not make SoS solvable in polynomial bit complexity, we construct complete truncated Groebner bases for the soft Majority ideal and show that, at every fixed degree $2d$, the relaxation can be optimized to any rational accuracy in polynomial time with exactly feasible solutions, and degree-$2d$ SoS proofs can be found after an additive perturbation at degree at most $4d+10$. The lower bound combines Raghavendra's gap-to-hardness theorem with an integrality gap on a Gaussian star, analyzed via the Isaksson-Mossel theorem that parallel halfspaces maximize the joint membership probability of exchangeable Gaussians.

0.44

A Polynomial Time Approximation for the Minimization of Implication Systems and Horn CNFs

cs.DM ·2026-11-15 ·Endre Boros, Ondrej Cepek, Kazuhisa Makino
similarity 0.64
Abstract

An implication system is a collection of rules of the form $B \imp H$, where the set $B$ of Boolean variables is the {\em body} of the rule, while $H$ is the set of its {\em heads}. Such a rule is an aggregate representation of individual implications $B\imp h$, for $h\in H$ which correspond to the clauses of an equivalent CNF representation of a Horn Boolean function. An implication system is {\em body-minimum}/{\em clause-minimum} if it has the minimum number of bodies/clauses among all logically equivalent implication systems. The corresponding minimization problems appear not only in the context of implication systems, but also as problems for closure systems, directed hypergraphs, representation of dependencies in relational databases, or in Horn CNF minimization. While body-minimization is known to be solvable in polynomial time (and there are several algorithms in the literature that solve this task), clause-minimization is known to be NP-hard. In fact, body-minimization has a particular canonical solution, called the GD-basis of the underlying Horn function that also can be computed efficiently. In this paper, we utilize a known connection between the two minimization problems stating that for every implication system there always exists a logically equivalent clause-minimum implication system which has the same bodies as its canonical GD-basis, see (B{é}rczi and B{é}rczi-Kov{á}cs, 2017), and (Adaricheva and Nation, 2014). We use this fact to design a polynomial time approximation algorithm which for any $δ>0$ outputs a $(\frac{1}{4} + δ)n$-factor approximation of the logically equivalent clause-minimum implication system on $n$ variables. This is an improvement from the best known algorithm so far that provides only an $(n-1)$-factor approximation, see (Hammer and Kogan, 1993).

0.30

SAT-based Encodings for Optimal Decision Trees with Explicit Paths

cs.LO ·2026-08-20 ·Mikoláš Janota, António Morgado
top venuehighly cited similarity 0.64
Abstract

Decision trees play an important role both in Machine Learning and Knowledge Representation. They are attractive due to their immediate interpretability. In the spirit of Occam's razor, and interpretability, it is desirable to calculate the smallest tree. This, however, has proven to be a challenging task and greedy approaches are typically used to learn trees in practice. Nevertheless, recent work showed that by the use of SAT solvers one may calculate the optimal size tree for real-world benchmarks. This paper proposes a novel SAT-based encoding that explicitly models paths in the tree, which enables us to control the tree's depth as well as size. At the level of individual SAT calls, we investigate splitting the search space into tree topologies. Our tool outperforms the existing implementation. But also, the experimental results show that minimizing the depth first and then minimizing the number of nodes enables solving a larger set of instances.

0.68

Solving Restricted Versions of #SAT Faster than $2^m$: Algorithms and Lower Bounds

cs.DS ·2026-10-11 ·Sanjay Jain, Junqiang Peng, Frank Stephan, Mingyu Xiao
similarity 0.64
Abstract

Under the Strong Exponential Time Hypothesis (SETH), for any constant $\varepsilon > 0$, the #SAT problem (counting the number of satisfying assignments of a CNF formula) cannot be solved in $\mathcal{O}^*((2-\varepsilon)^n)$ or $\mathcal{O}^*((2-\varepsilon)^m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. On the other hand, simple exhaustive search and the standard inclusion-exclusion give $\mathcal{O}^*(2^n)$-time and $\mathcal{O}^*(2^m)$-time algorithms, respectively. A natural line of research is to beat these SETH-based barriers for restricted versions, such as #$k$-SAT (where each clause contains at most $k$ literals) or #$d$-occ-SAT (where each variable appears in at most $d$ clauses). It is known that the $2^n$-barrier can be broken when $k$ or $d$ is any constant; yet, whether the $2^m$-barrier can also be broken in these cases remains unknown. We present two simple algorithms that overcome the $2^m$-barrier. First, for #$k$-SAT, we give an $\mathcal{O}^*(2^{m(1-1/O(k))})$-time algorithm, thereby breaking the $2^m$-barrier for any constant $k$. Second, for #$2$-occ-SAT (which also includes the problem of counting the number of edge covers in a graph as a special case), we provide an algorithm with runtime $\mathcal{O}^*(2^{mω/3})$, where $ω< 2.3714$ is the matrix multiplication exponent. Furthermore, we demonstrate that both algorithms generalize to the weighted counting setting while preserving the same runtime bounds. On the hardness side, we present a reduction from #Max-$d$-SAT to #$d$-occ-SAT, showing that for any $d\ge 3$, #$d$-occ-SAT admits no $\mathcal{O}^*((2-\varepsilon)^m)$-time algorithm for any constant $\varepsilon>0$, even on positive formulas, under the hypothesis that #Max-3-SAT on $n$ variables admits no $\mathcal{O}^*((2-\varepsilon)^n)$-time algorithm for any such $\varepsilon$.

0.29

Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by Treewidth

cs.DS cs.CC ·2026-11-12 ·Jakob Greilhuber, Dániel Marx, George Osipov, Marta Piecyk, Paweł Rzążewski +1 more
similarity 0.63
Abstract · The abstract has been truncated for arXiv

We consider valued constraint satisfaction problems (VCSPs) with a fixed finite domain $D$ and a fixed finite constraint language $Γ$, in the setting where $Γ$ contains all crisp unary constraints (called hard lists) and the remaining cost functions are finite-valued. We call such a language a finite-valued hard-list language. Let $c_Γ$ be the size of the largest set $S\subseteq D$ such that $Γ$ can express (using the usual VCSP closure operations) a binary disequality function on elements of $S$. Our main result tightly connects the complexity of the problem parameterized by treewidth to this value $c_Γ$. (1) The problem can be solved in time $(c_Γ)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)}$ when given an instance $I$ with a tree decomposition $\mathcal{T}$ of width $\mathsf{tw}$ of the primal graph of $I$. (2) If $c_Γ\geq 2$, there is no such algorithm solving the problem in time $(c_Γ- \varepsilon)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)}$ for any $\varepsilon > 0$, unless the Primal Treewidth SETH (and hence CNF-SETH) fails. In particular, this gives a far-reaching generalization of a similar result of Esmer et al. [ESA 2024] on the optimization version of list homomorphism for graphs.

0.23

A Uniform Algorithm for Strict NP on Bounded-Treedepth Graphs

cs.DS cs.CC ·2026-10-05 ·Thomas Depian, Robert Ganian, Jakob Greilhuber, Marlene Gründel, Simon Wietheger
similarity 0.63
Abstract

A classical well-quasi-ordering result guarantees the existence of non-uniform linear-time algorithms for all problems in Strict NP on relational structures of bounded treedepth; however, this provides neither a procedure for constructing these algorithms nor computable bounds on their parameter dependence. We turn this existential result into a uniform algorithmic metatheorem. Given a Strict NP sentence $\varphi$ and a relational structure $\mathcal{R}$, our algorithm decides whether $\mathcal{R}\models\varphi$ in time $f(|\varphi|, td(\mathcal{R})) \cdot |\mathcal{R}|$ for a computable function $f$, where the treedepth of $\mathcal{R}$ is measured on the Gaifman graph. The algorithm also constructs witness relations, with the polynomial exponent depending on their arity, and provides a unified framework for settling hereditary graph problems parameterized by treedepth. We also present several applications - among others, our result resolves open questions on the fixed-parameter tractability of computing the stack number, queue number, track number and twin-width parameterized by treedepth.

0.29