CS Paper Radar

Separating comb inequalities is NP-hard

Yohan Finet, Victor Drouin-Touchette

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

Abstract

Comb inequalities are important cutting planes for the symmetric travelling salesman problem, yet the complexity of their exact separation has remained a longstanding question in polyhedral combinatorics. We present a reduction from 3-SAT proving that deciding whether a comb inequality is violated is NP-complete and that the corresponding separation problem is NP-hard. This result holds even when the input vector belongs to the subtour elimination polytope, every edge value is zero, one half or one and the support graph is nonplanar with maximum degree four. The reduction constructs a graph in which six-vertex ladder gadgets encode Boolean relations and cubic graphs enforce consistency among occurrences of each logical variable. For a propositional logic formula with $v$ variables and $m$ clauses, the constructed graph has $40v+70m+30$ vertices and a linear number of positive edges. The reduction also proves hardness when every permitted tooth has two or four vertices with half of the tooth in the handle. We discuss consequences for approximating the maximum comb violation, optimization over the comb relaxation and explain why hardness of separation does not automatically transfer to larger inequality families.

Closest papers

Nearest neighbours by meaning across the whole index.

The canonical facets of multi-separator polytopes

cs.DM cs.LGmath.CO ·2026-08-17 ·Bjoern Andres, Silvia Di Gregorio, Jannik Irmai, Lucas Fabian Naumann, Shengxian Zhao
similarity 0.66
Abstract · 49 pages, 19 figures

We initiate a polyhedral study of the graph multi-separator problem proposed by Irmai et al. (2024) as an alternative to the lifted multicut problem for application to the task of image segmentation. Starting with an integer linear program (ILP) formulation and the multi-separator polytope spanned by its feasible solutions, we characterize in terms of efficiently-decidable, graph-theoretic conditions all facets induced by inequalities of the ILP. We proceed by strengthening these inequalities and describing additional facets of some multi-separator polytopes induced by the stronger inequalities. Specifically, we obtain a totally dual integral description of the multi-separator polytope for paths in the case where separation is considered for all vertex pairs. Finally, we relate the multi-separator polytope to the boolean quadric polytope, showing that facets induced by odd-cycle inequalities do not transfer generally, and to the lifted multicut polytope, showing that either polytope is a projection of a face of the other.

0.36

An Improved Algorithm for Quantified Boolean Formulas

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

Smallest Cubic Non-1-Planar Graphs

cs.CG math.COcs.DM ·2026-09-23 ·Sergey Pupyrev
similarity 0.64
Abstract

A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such graphs are the Tutte-Coxeter graph of girth eight and a graph of girth seven that we call the Byte graph. Every subcubic graph with fewer than $30$ vertices is 1-planar. Our proof is computer-assisted, but directly testing all relevant graphs is impractical. To establish non-1-planarity of the two graphs, we extend a SAT-based solver with a custom clause propagator based on separating cycles and a case split based on graph automorphisms, allowing independent cases to be solved in parallel. To show that all smaller subcubic graphs are 1-planar, we introduce the concept of $k$-flexibility: every set of at most $k$ prescribed edges can remain uncrossed in some 1-planar drawing. We use this property to reconstruct 1-planar drawings of larger graphs from drawings of smaller $k$-flexible graphs. This replaces exhaustive testing of more than forty billion cubic graphs with computations on far fewer graphs of smaller order.

0.28

Important Cuts with Logical Constraints: A Meta-Theorem for Eulerian Digraphs

cs.DS ·2026-11-14 ·Václav Blažej, Satyabrata Jana, Jędrzej Olkowski, M. S. Ramanujan, Peter Strulo
top venuetheory similarity 0.63
Abstract · To appear at SODA 2027

Important separators are a standard tool in parameterized cut algorithms. An $S$-$T$ separator is important if it is inclusion-wise minimal and no separator of at most the same size leaves a strict superset of the vertices reachable from $S$ after deletion. Their use relies on a boundedness theorem: for fixed $k$, the number of important $S$-$T$ separators of size at most $k$ is at most a constant ($4^k$ to be precise) independent of the input size, even in directed graphs, and they can be enumerated efficiently. The classical theory, however, controls only the size of the separator, not the structure of the source side cut off by it. Once the source side is required to satisfy a condition such as acyclicity, bipartiteness, or another logical property, the corresponding maximal source sides can be unbounded in general digraphs. This obstruction is fundamentally related to hardness phenomena in directed deletion problems such as Directed Odd Cycle Transversal}. Prior to this work, even in undirected graphs, boundedness of such maximal constrained source sides was known only in more specialized settings, not at the level of generality considered in our work.

0.64

Combinatorial optimization with bounded subdeterminants

cs.DS cs.DMmath.COmath.OC ·2026-11-09 ·Samuel Fiorini, J. Pascal Gollin, Tony Huynh, Simon Keil, O-joung Kwon +3 more
similarity 0.63
Abstract · 25 pages

We take a first step toward a broader study of classical combinatorial optimization problems through the maximum subdeterminants of their standard integer programming formulations, yielding new positive results for several famous (NP-hard) problems. An integer matrix is totally $Δ$-modular if every square submatrix has determinant of absolute value at most $Δ$. For every fixed $Δ$, it has been known that maximum clique, maximum stable set, and minimum vertex cover can be solved in polynomial time on instances for which the coefficient matrix of the natural formulation is totally $Δ$-modular. We extend this list by showing that the same holds for many other problems, including the weighted versions of maximum cut, the traveling salesman problem, feedback vertex set, odd cycle transversal, dominating set, max 2-sat, induced matching, and cluster vertex deletion, as well as for $k$-colorability and graph isomorphism. Our proofs reveal several new ways in which bounded subdeterminants impose combinatorial structure: they bound the size or maximum degree of the input graph, bound packings of cycles and other obstructions, or yield decompositions into tractable graph classes such as forests, chordal graphs, graphs of bounded treewidth, and graphs of bounded linear mim-width.

0.20

A PTAS for Constraint Satisfaction Problems on Interval Graphs and Bounded Rank-Width Graphs

cs.DS ·2026-11-12 ·Ian DeHaan, Euiwoong Lee
similarity 0.62
Abstract · 18 pages

We present a polynomial-time approximation scheme (PTAS) for all Boolean arity-two maximum constraint satisfaction problems (Boolean Max-2-CSP) where the constraint graph is either interval or has bounded rank-width. This class of problems includes, for example, Max-Cut, Max-DiCut, Max-2-Lin(2), and Max-2-SAT. In particular, this settles the approximability of Max-Cut on interval graphs. To achieve these results, we show the following. 1. For any $\varepsilon > 0$, there is an $n^{\mathcal O(r \varepsilon^{-2})}$-time $(1 - \varepsilon$)-approximation for Boolean Max-2-CSP on graphs of rank-width at most $r$. 2. There is a polynomial-time algorithm that, for any interval graph $G = (V, E)$ and $\varepsilon > 0$, finds a subgraph $H = (V, F)$ of $G$ such that $|F| \geq (1 - \varepsilon) |E|$ and $H$ has rank-width at most $\operatorname{poly}(\varepsilon^{-1})$. Our techniques additionally extend to all bounded-alphabet arity-two max CSPs.

0.28

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

cs.CC cs.DS ·2026-08-20 ·Takashi Horiyama, Shoon Mineyoshi, Yuto Okura, Kazuhisa Seto, Junichi Teruyama
theory similarity 0.61
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.

0.26

Solving Large SDPs from Flag Algebra Problems

cs.DM math.CO ·2026-10-24 ·Bernard Lidický, Jan Volec
theory similarity 0.61
Abstract · 17 pages, 2 figures

The flag algebra method is a general tool in extremal combinatorics, which has been useful in tackling open problems concerning graphs, hypergraphs, permutations, point sets, and other structures. The method establishes combinatorial inequalities via sums of squares, which are usually obtained by a semidefinite relaxation of the original combinatorial problem. A typical application of the method in graph theory starts with fixing a parameter $n$ followed by constructing a semidefinite program based on the (subgraph) structure of all $n$-vertex graphs. In the standard formulation before symmetry reductions, there is a coefficient constraint for every admissible $n$-vertex graph up to isomorphism. For 3-uniform hypergraphs, there are 2,136 of them on 6 vertices and 7,013,320 on 7 vertices. While solving the resulting program for $n=6$ is an easy task on any modern computer, the programs for $n = 7$ seems out of reach, mainly because the SDP solvers need too much RAM. Yet solving such programs for as large $n$ as possible is desirable because they typically yield better bounds for the original combinatorial problems. We bypass the aforementioned memory requirements by linear programming with cutting planes. Although we do not guarantee that this cutting-plane procedure reaches an optimum in finitely many iterations, in many flag algebra instances it uses much less memory and yields improved bounds for well-known hypergraph Turán problems. We use this method to obtain numerical bounds for Turán densities and codegree squared densities of several 3-uniform hypergraphs including the tetrahedron, where we obtained the upper bound 0.55753 and tetrahedron without one edge with a new upper bound 0.2865. It also allows to tackle bounds on Turán densities of 7-vertex 3-graphs using flag algebras, which was not possible before.

0.46