CS Paper Radar

The Complexity of Boolean Connectivity Problem of $k$-Horn Formulas

Takashi Horiyama, Shoon Mineyoshi, Yuto Okura, Kazuhisa Seto, Junichi Teruyama

cs.CC cs.DS ·submitted 2026-08-20 02:14 UTC · v1
theory

Abstract

The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the $n$-dimensional hypercube. This problem is known to be $\mathsf{coNP}$-complete, even when restricted to $k$-Horn formulas for $k \geq 3$, as shown by Makino, Tamaki, and Yamamoto. In this paper, we further investigate the computational complexity of {\sc Conn $k$-Horn}, the Boolean connectivity problem for $k$-Horn formulas. We provide algorithmic and hardness results for {\sc Conn $k$-Horn}. On the algorithmic side, we first present an exact exponential-time algorithm for arbitrary $k$ without any structural restrictions. Our algorithm builds on the deterministic PPZ algorithm proposed by Paturi, Pudlák, and Zane. It runs in $O^*(2^{(1 - 1/2k)n})$ time and polynomial space, achieving an exponential improvement over the previously known algorithm for the Boolean connectivity problem of $k$-CNF formulas, shown by Makino, Tamaki, and Yamamoto. We next give two polynomial-time algorithms for arbitrary $k$ under the following two restrictions: (i) each variable appears at most twice, and (ii) each clause has length exactly $k$ and each variable appears at most $k$ times. On the hardness side, we prove that {\sc Conn $3$-Horn} remains $\mathsf{coNP}$-complete even when each variable appears exactly three times.

Closest papers

Nearest neighbours by meaning across the whole index.

Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem

cs.DS math.CO ·2026-08-31 ·Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani, Soheil Mohammadkhani
theory similarity 0.72
Abstract

We give the first polynomial-time algorithm, after half a century, for the celebrated Győri-Lovász theorem, which resolved a conjecture of Frank (1975). The theorem, one of the simplest existential theorems to explain, states that every $k$-connected graph can be partitioned into $k$ disjoint connected subgraphs of arbitrary prescribed positive sizes. This is a fundamental structural result with broad applications, such as flexible allocation of connected subnetworks of prescribed sizes in sufficiently connected cloud infrastructures. While Lovász (1977) gave a highly non-constructive proof for a stronger directed version using algebraic topology, Győri's original constructive proof (1976) requires exponential time. Despite more than 50 years of effort, no polynomial-time algorithm was known even for $k>4$. Determining the computational complexity of the Győri-Lovász theorem---whether it admits even a sub-exponential-time algorithm or is computationally hard (in particular, PLS-complete or PPAD)---has remained one of the central open problems in algorithmic graph theory. In this paper, we finally resolve this long-standing problem by a fundamentally new proof of the existential theorem via introducing the novel concept of \emph{flow-essential assignment}, which genuinely marries matching and cut structures and yields the first polynomial-time constructive algorithm for the Győri-Lovász theorem. In fact, we obtain a polynomial-time algorithm for Lovász's stronger directed version, whose proof was non-constructive even for DAGs; for DAGs, we further obtain a near-linear-time algorithm. We also develop polynomial-time algorithms for weighted generalizations where the seminal work of Chen, Kleinberg, Lovász, Rajaraman, Sundaram, and Vetta (JACM'07) on confluent flows established only existential non-constructive results.

0.37

An Improved Algorithm for Quantified Boolean Formulas

cs.DS cs.AI ·2026-11-07 ·Zhiyang Chen, Hailong Yao
similarity 0.67
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

Finding Hypercliques Faster Than Brute Force

cs.DS cs.CC ·2026-11-03 ·Josh Alman, Baitian Li, Neha Pant, Kevin Pratt, Ryan Williams
similarity 0.65
Abstract

We show that for any fixed $k$, there exists $\varepsilon_k > 0$ such that, given a $(k-1)$-uniform hypergraph $H$ on $n$ vertices, one can count the number of $k$-hypercliques in $H$ in $O(n^{k-\varepsilon_k})$ time. This refutes the hyperclique conjecture of Lincoln, Vassilevska Williams, and Williams (SODA 2018). Our result follows from the uniform construction of a family of arithmetic circuits of size $O(n^{k-\varepsilon_k})$ for the $k$-hyperclique tensor, a natural higher-order generalization of the matrix multiplication tensor. We obtain two corollaries. First, for every $k$, there exists $\varepsilon > 0$ such that Max-$k$SAT can be solved in $2^{(1-\varepsilon)n} \cdot \mathrm{poly}(m,n)$ time. Second, for every $k$, there exists $\varepsilon > 0$ such that arithmetic progressions of length $k$ in subsets of $\{0,1,\ldots,n\}$ can be detected in $n^{2-\varepsilon}$ time. Both corollaries refute other prominent conjectures in the literature.

0.23

Sub-polynomial parameterized complexity of $k$-core

cs.CC ·2026-09-21 ·Yan S. Couto, Cristina G. Fernandes
theory similarity 0.65
Abstract

The $k$-core of a graph is its (unique) largest subgraph with minimum degree at least $k$. For any $k \geq 3$, deciding whether a given vertex belongs to the $k$-core is a P-complete problem, meaning that it is inherently sequential and highly unlikely to admit efficient parallel algorithms, even on graphs of maximum degree $k+1$. This paper investigates alternative parameterizations of the $k$-core problem to identify conditions under which it can be placed into sub-polynomial complexity classes. We prove that the problem is in para-NC$^{2+ε}$ when parameterized by treewidth, and in para-NC$^3$ when parameterized by $k$ on chordal graphs. Furthermore, we introduce a novel NC$^{3}$ algorithm for interval graphs when $k = \mathcal{O}(\lg v(G))$, which relies on an improved parameterization by pathwidth. Finally, we establish corresponding lower bounds, demonstrating that, even with these parameterizations, computing the $k$-core remains L-hard, meaning it requires at least logarithmic space. These findings explore the boundary of parallel tractability for the $k$-core problem by highlighting the graph parameters that make it inherently sequential.

0.23

A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems

cs.CC ·2026-09-06 ·Chenghua Liu, Boning Meng, Juqiu Wang
theory similarity 0.64
Abstract · 98 pages; proof and exposition revised, Lean repository linked

A Boolean Holant problem evaluates a graph partition function specified by local signatures at its vertices. We prove a complexity dichotomy for arbitrary finite sets of algebraic complex-valued signatures on general graphs: an explicit, decidable criterion characterizes the polynomial-time cases, and every remaining case is $\#\mathsf{P}$-hard under polynomial-time Turing reductions. The proof resolves the all-even case by constructing signatures with nonzero endpoints and all remaining support on the central layer, then classifying them according to half their arity. Binary transfer groups and matching-product reconstruction provide the main tools in the small- and large-height cases, respectively.

0.24

Min-CSPs on Complete Instances III: Nearly Optimal Characterizations of Approximation for Symmetric CSPs

cs.DS ·2026-11-10 ·Yihwan Chae, Chenglin Fan, Donghyeon Lee, Euiwoong Lee
similarity 0.64
Abstract · 45 pages. Adjusted the placement of Table 1

This paper studies complete Min-$k$-CSPs: an instance on $n$ variables has one nontrivial constraint for every $k$-set of variables (so $\binom{n}{k}$ constraints in total), and the goal is to find an assignment that minimizes the number of unsatisfied constraints. They are motivated by the connections to machine learning and data science, as well as the possibility of being testbeds for new algorithmic techniques. Previous recent results presented polynomial-time algorithms for the decision version of every complete Boolean $k$-CSP, which is a necessary condition for any multiplicative approximations for the minimization version, but nontrivial approximation results have been limited to fragile CSPs, 2-SAT, and NAE-3-SAT, leaving the approximability of most complete Boolean Min-CSPs open, including complete Min-$k$-SAT. In this paper, we resolve this question, up to nearly matching factors, for the natural class of symmetric Boolean predicates. Given $A \subseteq \{0, \dots, k\}$, Min-CSP($A$) is a Min-$k$-CSP where each constraint is specified by $k$ literals and is satisfied if the number of true literals belongs to $A$. Let $w(A)$ be the maximum number of consecutive integers in $A$. Our main results for complete Min-CSP($A$) are (1) a QPTAS for $w(A) \leq 2$ and (2) an $\widetilde{O}(n^{w(A)-3})$-approximation for $w(A) \geq 3$, as well as almost matching hardness results for the latter. Our QPTAS for $w(A)=2$ significantly improves the previous $O(1)$-approximation for Min-2-SAT and the $\operatorname{polylog}(n)$-approximation for Min-NAE-3-SAT, as well as extends the PTAS for fragile CSPs (i.e., $w(A) = 1$).

0.23

A note on the intractability of enumerating the maximal satisfiable subformulas of a Horn expression

cs.DM cs.DSmath.CO ·2026-11-10 ·Oscar Defrain, Corentin Jazeron, Kazuhisa Makino
hot direction similarity 0.63
Abstract · 6 pages

We show that, given a Horn expression and a family of inclusion-wise maximal satisfiable subsets of its clauses, deciding whether there exists another maximal satisfiable subset is NP-complete. As a consequence, unless P=NP, there is no output-polynomial time algorithm enumerating the maximal satisfiable subformulas of a Horn expression.

0.34

Forbidden Subgraphs of Graphs with Low Bandwidth

cs.DS ·2026-09-01 ·Maria Chudnovsky, Daniel Lokshtanov, Eran Nevo
top venuetheory similarity 0.63
Abstract

A layout of a graph G is an injective function $f : V(G) \rightarrow Z$, and the bandwidth of a layout f is $bw(G,f) = max_{uv \in E(G)} |f(u) - f(v)|$. The bandwidth bw(G) of G is the minimum bandwidth of a layout of G. Computing the bandwidth of a graph is a notoriously hard problem: assuming P != NP, there is no polynomial time algorithm, even on very restricted classes of trees [Monien, SIAM Journal on Algebraic Discrete Methods, 1986], and no constant factor approximation, even on trees [Dubey et al., JCSS 2011]. Assuming the Exponential Time Hypothesis, there is no algorithm with running time $f(k)n^{o(k)}$ to determine whether an input graph has bandwidth at most k, even on very restricted classes of trees [Dregi and Lokshtanov, ICALP 2014]. In this paper we show that {\sc Bandwidth} on general graphs is FPT-approximable. In particular we give an algorithm that takes as input a graph G and an integer k, runs in time $2^{O(9^k)}n^{O(1)}$, and outputs a subtree T of G such that $bw(T) \geq k$ or a layout of G of bandwidth at most $(10^{85} k^{28})^{4^k}$. This resolves in the affirmative an open problem of Chung and Seymour [Discrete Mathematics, 1989], who asked whether the bandwidth of every graph G is upper bounded in terms of the maximum bandwidth of a subtree of G. Our theorem leads to a forbidden subgraph characterization for graphs of bounded bandwidth, and can be seen as an analog for bandwidth of the classic grid minor theorem for treewidth, the forbidden subtree theorem for pathwidth, and the forbidden subpath theorem for treedepth.

0.54