CS Paper Radar

Exact SAT Solving for the Two-Dimensional Bandwidth Minimization Problem

Pham Quang Minh, Dao Xuan Nghia, To Van Khanh

cs.LO cs.DMmath.CO ·submitted 2026-08-19 04:03 UTC · v1
benchmark

Abstract

The two-dimensional bandwidth minimization problem (2DBMP) seeks an injective embedding of a guest graph into a square grid that minimizes the maximum Manhattan distance over its edges. Heuristic methods can provide strong upper bounds, but these bounds do not by themselves certify optimality. We present an efficient exact SAT-based approach for 2DBMP that incrementally searches for the minimum feasible bandwidth and certifies optimality through satisfiability and unsatisfiability results. On the standard $\lceil\sqrt n\rceil \times \lceil\sqrt n\rceil$ host grid, under a 3600 s time limit, the proposed SAT approach certifies optimal bandwidths for 41 of 43 Regular instances and 42 of 93 Harwell--Boeing instances, achieving substantially broader optimality certification within the 3600 s time limit than a previous exact approach evaluated with a 72-hour time limit. In addition, it certifies three bandwidth values that improve all previously published comparison values considered in this study and establishes all three as optimal. We further evaluate the approach on alternative host geometries, namely $2\times\lceil n/2\rceil$ and $n\times n$ grids, to assess its effectiveness beyond the standard host. Overall, the results demonstrate that the proposed SAT approach provides an effective exact method for the small- and medium-sized benchmark instances considered in this study, with fewer than 400 vertices, while heuristic methods remain important for larger and more challenging instances.

Comment
30 pages, 10 figures, 9 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Geometric Graph Representations via Compact SAT Encodings

cs.CG cs.DMcs.DScs.LO+1 ·2026-10-15 ·L. Sunil Chandran, Rishikesh Gajjala, Suraj Kumar Sahoo, Aatman Supkar
publishedtheory similarity 0.61
Abstract · To appear in ALENEX 2027

We present compact SAT encodings and certifying exact solvers for boxicity and cubicity. The boxicity of a graph is the minimum dimension in which it is the intersection graph of axis-aligned boxes; cubicity is defined analogously using unit cubes. Grid-based formulations face a geometric discretization bottleneck, growing rapidly with the target dimension. We avoid this bottleneck by encoding the total order of interval endpoints in each coordinate. For an $n$-vertex graph and target dimension $d$, our boxicity encoding uses $O(n^2d)$ variables and $O(n^3d)$ clauses, both linear in $d$. Requiring the left- and right-endpoint orders to agree yields a cubicity encoding of the same asymptotic size. Satisfying models are decoded into independently checked geometric representations, while unsatisfiable instances used as lower-bound evidence carry mechanically verified DRAT certificates. In a controlled evaluation with 186 trials per encoding on standard and structured graph families, the order encoding solves 96.8% of trials, compared with 71.0% for the known grid formulation, and reduces mean PAR-2 time from 178.21 to 21.70 seconds. The pipeline also certifies exact values for several named graphs. We turn one such value into a reusable obstruction by proving that every Kneser graph $K(n,k)$ with $k\ge3$ and $n\ge2k+1$ contains an induced Desargues graph. The resulting lower bound, together with an explicit three-dimensional representation of $K(7,3)$, establishes $\operatorname{boxicity}(K(7,3))=3$. This disproves the conjecture of Caoduro and Sebo that $\operatorname{boxicity}(K(n,k))=n-k$ for all $k\ge3$ and $n\ge2k+1$.

0.59

Solving Minimum Span Antibandwidth and Cyclic Antibandwidth Labeling Problems

cs.AI ·2026-09-17 ·Hieu Truong Xuan, Khanh To Van
benchmark similarity 0.61
Abstract

The Antibandwidth and Cyclic Antibandwidth problems are NP-hard graph labeling problems that aim to maximize the minimum (cyclic) distance between labels assigned to adjacent vertices. Extensive research on these problems has resulted in a variety of mathematical formulations and computational approaches. However, their minimum span perspective, in which a prescribed minimum (cyclic) distance is fixed and the objective is to minimize the label span, has received comparatively little attention. In this paper, we consider this complementary perspective by introducing the Minimum Span Antibandwidth/Cyclic Antibandwidth Labeling (MSABL/MSCABL) problems and developing a unified Boolean Satisfiability (SAT)-based framework for solving them. The SAT-based framework formulates MSABL/MSCABL as a sequence of decision problems and exploits their monotonicity to accelerate the search process. We also consider two SAT solving strategies, parallel and incremental SAT solving: the former examines multiple candidate spans concurrently, while the latter reuses a single SAT instance while progressively restricting the label domain. The proposed approaches are evaluated on benchmark instances from the Harwell-Boeing Sparse Matrix Collection and compared with CPLEXCP, CPLEXMIP, and Gurobi. The results show that SAT-based approaches are highly competitive in solution quality, with the parallel approach performing best overall for MSCABL and the incremental approach for MSABL. With the no-hole constraint, they remain competitive with CPLEXCP and significantly outperform CPLEXMIP and Gurobi, particularly for MSCABL. These results demonstrate the effectiveness of SAT solving as an exact approach for MSABL and MSCABL.

0.26

Metric Planarity Testing is Hard

cs.DS ·2026-10-11 ·Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak, Hung Le, Bartłomiej Lewandowski +1 more
theory similarity 0.56
Abstract · 9 figures, 27 pages

A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for either a polynomial-time algorithm or an NP-hardness proof for metric planarity testing: given a metric space $(X,d_X)$, determine whether there exists an edge-weighted planar graph $G=(V,E,w)$ with $X\subseteq V$ that realizes the distances in $X$, meaning that $d_G(x,y)=d_X(x,y)$ for every $x,y\in X$. This question arose in the context of research on metric embeddings and their applications in computer science since the mid-1990s. Over the past few decades, polynomial-time algorithms have been developed for several special cases. In this work, we show that metric planarity testing is NP-hard, in sharp contrast to graph planarity testing. Our reduction yields a stronger result: under the Exponential Time Hypothesis (ETH), no $2^{o(n)}$-time algorithm for metric planarity testing exists, where $n$ is the number of points in the metric. To complement our ETH lower bound, we give two algorithmic results: (i) an algorithm for computing a metric planar embedding in $2^{\tilde{O}(n^2)}$ time and (ii) a $(1+ε)$-approximation algorithm in $2^{\tilde{O}(n)}$ time for any fixed $ε\in(0,1)$. The second algorithm produces a planar graph that preserves the input metric up to a factor of $(1+ε)$.

0.29

Parameterized Approximation for Minimizing Uncovered Elements and Unsatisfied Constraints

cs.DS ·2026-11-13 ·Rudranarayan Kar, Souvik Saha, Abhishek Sahu
theory similarity 0.55
Abstract

Min-UnCoverage asks for at most $k$ sets minimizing uncovered weight. Min-Unsat SAT and Min-Unsat CSP ask for an assignment with at most $k$ true variables minimizing the weight of unsatisfied clauses or constraints. For constraints of arity at most $d$, we give a deterministic $(1+\varepsilon)$-approximation for weighted Min-Unsat CSP in $(dk/\varepsilon)^{O(k)}N^{O(1)}$ time, where $N$ is the input size. This also gives approximation schemes for bounded-arity SAT and coverage with bounded element frequency. We show that weighted coverage with set size at most $d$ can be solved exactly in $2^{O(kd)}N^{O(1)}$ time by adapting color-coding. For coverage on incidence graphs of bounded semi-ladder index, we give a deterministic parameterized approximation scheme . We show that, unless $\mathrm{FPT}=\mathrm{W}[1]$, SAT and CSP have no finite-factor FPT approximation parameterized by $k+d$ when variable frequency is at most $d$, or on $K_{3,3}$-free incidence graphs of semi-ladder index at most four. Known Hitting Set hardness gives the same lower bound for all three problems at VC dimension two. Under the same assumption, we show that no computable relaxation $g(k,d)\geq k$ allows an FPT algorithm to preserve a prescribed unsatisfied-weight target for SAT or CSP, already for arity three and, separately, bounded variable frequency. For coverage, known algorithms preserve the target using at most $k+1$ sets on incidence graphs of bounded semi-ladder index.

0.28

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.54
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

Optimal Non-Adaptive Vantage Point Selection

cs.DS ·2026-09-09 ·Jie Gao, Nicole Wein, Chang Wu
theory similarity 0.53
Abstract

We study the \emph{vantage point selection} problem, introduced by Ashvinkumar, Chowdhury, Gao, Goswami, Mitchell, and Polishchuk [WADS'25] to model the problem of estimating bottleneck capacities on the Internet. The input is a weighted undirected graph with unique shortest paths where every edge has a distinct unknown \emph{capacity}. When the algorithm \emph{queries} a vertex $v$, it reveals the minimum-capacity edge on the shortest path from $v$ to every other vertex reachable from $v$. The goal is to maximize the total number of revealed edges. The quality of an algorithm is measured by its competitive ratio against an optimal algorithm that knows all edge capacities a priori. We first consider the foundational single-query setting, where both the algorithm and the optimal algorithm are restricted to a single query. There is a trivial upper bound of $O(n)$ on the competitive ratio and the best known lower bound was $\tildeΩ(\sqrt{n})$. We provide an algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible competitive ratio is $\tildeΘ(n^{2/3})$. Furthermore, we extend our results to the general setting where the optimal algorithm is allowed $k$ queries and our algorithm is allowed $αk$ queries for $α\geq 1$. We present a randomized non-adaptive algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible expected competitive ratio for non-adaptive algorithms is the following surprisingly complex bound: $$ \tildeΘ\left( \min\left\{ \frac{n}{αk}, \max\left( \sqrt{\frac{n}α}, \frac{n^{2/3}}{αk^{1/3}} \right) \right\} \right). $$

0.23

A two-stage approach to satellite constellation optimization: classical and QUBO formulations

eess.SY math.OC ·2026-10-01 ·Carlo Novara
similarity 0.52
Abstract · 17 pages, 1 figure, 1 table

The design of satellite constellations for Earth observation requires balancing spatial coverage, revisit time, cost, and operational complexity. This paper considers the problem of designing the orbits of a given number of Low Earth Orbit (LEO) or Very Low Earth Orbit (VLEO) satellites to maximize the spatial and temporal resolution achieved over a prescribed set of ground targets. This kind of problem is inherently nonconvex and possibly combinatorial, making its solution computationally demanding for large constellations and target sets. To address this challenge, we propose a two-stage optimization strategy that separates spatial-coverage design from temporal-resolution optimization, thereby reducing the complexity of the overall problem. Two variants of the method are developed. The first employs continuous decision variables during the spatial-optimization stage, whereas the second discretizes these variables and reformulates the problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The latter formulation enables the use of efficient classical QUBO solvers and is directly compatible with quantum-annealing hardware. The proposed framework provides a scalable approach to the design of heterogeneous LEO and VLEO Earth-observation constellations and establishes a pathway for exploiting emerging quantum-optimization technologies in satellite mission design. Preliminary simulation results are presented to demonstrate the effectiveness of the strategy.

0.26

Improved Deterministic Algorithms for $k$-SAT: Generalization of Chains and Recurrence Proof

cs.DS ·2026-11-12 ·Binbin Cui, S. Cliff Liu, Yongrui Yu
similarity 0.52
Abstract

We present a deterministic algorithm for 3-SAT running in $1.32736^n$ time. The algorithm is built on a branching-and-chain framework augmented with a polynomial-time expansion procedure that joins short chains through additional clauses to form bounded-size blocks, which impose stronger constraints on the assignment space. After branching, the algorithm chooses between derandomized local search guided by the block structure and enumeration of block assignments together with selected port variables, reducing the remaining formula to 2-SAT. A weighted analysis of branching, partial-assignment, and local-search costs, together with inductive bounds for chains and block interactions, establishes the running-time guarantee. The framework is self-contained and also offers guidance for practical SAT solver design by identifying useful clause-overlap structures and suggesting when to switch between local-search and reduction-based strategies.

0.27