CS Paper Radar

Path-constrained Packing on Trees

Samuel Fiorini, Raoul Luqué, Philipp Pabst, Britta Peis

cs.DS ·submitted 2026-11-16 14:04 UTC · v1

Abstract

An instance of Budgeted Path-constrained Packing on Trees (BPPT) consists of a graph $G$ together with a spanning tree $T$, a weight $w_e \in \mathbb{Z}_{\ge 0}$ for each tree edge $e \in E(T)$ and a budget $b_f \in \mathbb{Z}_{\ge 1}$ for each non-tree edge $f \in E(G) \setminus E(T)$. The goal is to find a maximum weight packing of fundamental cuts respecting the budgets. Equivalently, an instance of BPPT is an integer program of the form $\max \{w^\intercal x : Ax \le b,\ x \in \{0,1\}^n\}$ where $A \in \{0,1\}^{m \times n}$ is a transposed edge-path-tree matrix, $w \in \mathbb{Z}^n_{\ge 0}$ and $b \in \mathbb{Z}^m_{\ge 1}$. We define the congestion $C$ of a BPPT instance as the maximum number of non-zeros in a column of $A$. The unit congestion $UC$ is defined similarly, except that rows with $b_i \ge 2$ are ignored. We also consider the minimum budget $β:= \min \{b_i : i = 1, \ldots, m\}$. In this paper, we begin the study of BPPT through the lens of the three parameters $C$, $UC$ and $β$, and relative to the standard LP relaxation $\max \{w^\intercal x : Ax \le b,\ x \in [0,1]^n\}$. BPPT generalizes the independent set problem in graphs of maximum degree at most $C$ and is a special case of the $b$-matching problem in hypergraphs of rank at most $C$. We obtain approximation algorithms for BPPT with factors $2+UC/2$, $1+C/2$ and $β/(β-1)$ for $β\geq 2$. These bounds are relative to the standard LP relaxation and, as we show, integrality gap tight with respect to parameters $UC$ and $β$, and almost integrality gap tight relative to $C$. We complement these results with a $\lceil (C+1)/3 \rceil$-approximation for fixed $C$ which is not relative to the standard LP relaxation and has $\textsf{XP}$ running time parameterized by $C$.

Comment
36 pages, 5 figures, 1 table, 2 algorithms

Closest papers

Nearest neighbours by meaning across the whole index.

A Compact Weight-Space Integer Programming Formulation for Balanced Minimum Evolution

cs.DM ·2026-10-08 ·Leonid Chindelevitch, Matthew Penn, Samir Bhatt
benchmark similarity 0.67
Abstract · 44 pages, 1 figure

Balanced Minimum Evolution (BME) reconstructs an unrooted binary phylogenetic tree from a distance matrix $D$ by minimizing the length $\sum_{i<j}D_{ij}w_{ij}$, which is linear in the weights $w_{ij}=2^{-d_T{ij}}$. We study the formulation of BME in these $\binom{n}{2}$ weight variables. Theoretical results. (i) For a fixed topology $T$, the Kraft equalities, the cut equalities $\{W[S]=\tfrac12\}$ of $T$, and the single convex constraint $\sum w_{ij} \log_2 w_{ij} \leq \tfrac{3}{2}-n$ admit exactly one point, the tree's weight vector. (ii) For every tree and every bipartition, the cut value $W_T[S]$ lies in $\{\tfrac{1}{2}\} \cup \{\tfrac{3}{4}\} \cup [\tfrac{7}{8}, \infty)$; the value $\tfrac{3}{4}$ is attained exactly by the $2(n-3)$ bipartitions created by one nearest-neighbour interchange; and the number of bipartitions with $W_T[S]\le1$ is $2n^2-10n+15$ for every binary topology. (iii) The crossing graph of nontrivial bipartitions has an edge clique cover with $O(n^4)$ cliques, and every edge clique cover needs $Ω(n^2)$. (iv) The necessary conditions of Catanzaro et al. for a path-length matrix, without the four-point condition, are sufficient for $n \leq 11$ and first fail at $n=12$. Computational results. A compact branch-and-bound solver built on these results, which commits and forbids splits and imposes the convex constraint exactly, certifies optimality on benchmark instances with up to $n=20$ taxa within an hour. It is faster than the distance-indexed model of Catanzaro et al. on two of these instances and slower on the others; that model, whose root bound is tighter, certifies 13 of 14 benchmark instances with $n \leq 30$ within an hour in every seed. Although the compact solver does not improve on the computational state of the art overall, we explain why, and we discuss the open problems that our results raise.

0.30

High-Multiplicity Bin Packing is FPT

cs.DS ·2026-09-15 ·Tomohiro Koana, Soh Kumabe
similarity 0.63
Abstract

Bin packing asks whether a collection of items can be packed into at most a given number of bins of a given capacity. We consider the high-multiplicity setting with $d$ distinct item sizes, in which both the item sizes and the number of items of each size are encoded in binary. Goemans and Rothvos (JACM 2020) gave an XP algorithm parameterized by $d$. Whether this problem is fixed-parameter tractable (FPT) in $d$ has remained a central open problem. We resolve this question by giving a deterministic $O^*(2^{d^{O(d)}})$-time algorithm. We formulate bin packing as an integer linear program (ILP) with at most $(d+1)d^d$ variables. A bin configuration records the number of items of each type in one bin. We partition these configurations by their coordinate remainders modulo $d$. For each class, we use one variable for the bin count and $d$ variables for the total item counts. The convex hull of each class has the integer decomposition property, which guarantees that every feasible ILP solution corresponds to a packing.

0.56

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

The Complexity of Recognizing SDP Exactness for the Maximum Cut Problem

cs.CC math.OC ·2026-09-03 ·Avinash Bhardwaj
similarity 0.62
Abstract

The standard semidefinite programming (SDP) relaxation of Max-Cut is exact when its optimum equals the maximum cut value. Delorme and Poljak resolved NP-completeness of recognizing exactness for weighted graphs and left the unweighted case open. We show that recognition is NP-complete even for connected simple unweighted graphs, and hence strongly NP-complete for nonnegative integer edge weights. The reduction provides an explicit SDP optimum and makes the additive integrality gap equal to the minimum number of unsatisfied clauses in the source formula. Recognition remains NP-complete even when an exact rational optimal primal--dual pair is supplied. We also establish strong NP-hardness of recognizing exactness of the Frieze--Jerrum Max-$k$-Cut relaxation for every fixed $k\ge3$, even for connected graphs with nonnegative integer edge weights. An independent bounded-weight construction gives a second proof for Max-Cut. Finally, reductions preserving the additive gap up to explicit factors establish strong NP-completeness of exactness recognition for a basic Max-DiCut SDP and NP-hardness for a Max-Bisection SDP.

0.32

Entropic Column Generation and Lehmer Branch-and-Price for Bin Packing Problem

cs.DM math.OC ·2026-10-31 ·Masoud Ataei
benchmarkcode/data similarity 0.61
Abstract · 38 pages, 1 figure, 8 tables. Code: https://github.com/chimera1001/lehmer-bp

We introduce Lehmer branch-and-price, an exact algorithm for bin packing and cutting stock problems built on the Lehmer transform, the ratio of Mellin transforms of item weights at consecutive orders. The transform maps each bin, a finite multiset of item weights, to a smooth increasing curve, and so gives the discrete problem a continuous representation on which the tools of analysis, such as convexity, exponential families and smoothing, can act. Read along this curve, the problem yields an explicit dual solution, a monotone representation of the dominance order, a family of constructive heuristics with first fit decreasing as its limit, and an integer identity that tells when the linear relaxation can decide an instance and when only a perfect packing can improve the best solution known. Lifted from items to patterns, the transform gives entropic column generation, a new form of column generation that bounds the relaxation from both sides at every iteration without solving the pricing problem exactly, maximizes a smoothed dual at an explicit rate, and measures by an entropy how much the relaxation leaves undecided. We show that the proposed algorithm outperforms the state-of-the-art methods on the standard benchmark in both the number of instances solved and the computational time.

0.40

Two $(2+ε)$-Approximation Algorithms for Minimum Spanning Tree Interdiction

cs.DS ·2026-11-18 ·Junjie Luo, Changjun Wang, Chenhao Wang, Wei Yu
similarity 0.61
Abstract

Minimum spanning tree interdiction asks for edge deletions within a budget that maximize the weight of a remaining minimum spanning tree. We give two deterministic $(2+ε)$-approximation algorithms for every fixed $ε>0$, improving the previous best factor of $4$. Both algorithms respect the original budget and run in $N^{O(1/ε)}$ time for $0<ε\le1$, where $N$ is the binary input size. The first algorithm uses two weight thresholds to choose initial deletions that force every remaining spanning tree to contain edges at or above these thresholds. It then uses the remaining budget to further increase the MST weight through Lagrangian rounding. The second algorithm achieves the same guarantee through a different decomposition: it enumerates vertex partitions and heavy trees connecting their parts, then approximates a bounded-weight interdiction problem within the parts. An objective-preserving reduction from Maximum Components shows that, assuming the Small Set Expansion Hypothesis and $\mathsf P\ne\mathsf{NP}$, no deterministic polynomial-time $(2-δ)$-approximation exists for any fixed $0<δ<1$, even on simple graphs with weights in $\{0,1\}$. Thus, our approximation guarantee is conditionally tight up to an arbitrarily small additive constant. Finally, the MST guarantee yields a $(4+ε)$-approximation for metric-TSP interdiction.

0.15

Additive $Ω(\log^* OPT)$ Gap for Bin Packing with Three Items per Bin

cs.DS ·2026-11-06 ·Ilan Doron-Arad
theory similarity 0.61
Abstract

We prove that bin packing is NP-hard to approximate within an additive factor of $o(\ls\OPT)$, even when all item sizes are arbitrarily close to $1/3$. This gives the first lower bound for bin packing with an additive factor that depends explicitly on the optimum value. In addition, we give a polynomial-time reduction from any bin packing instance into one with item sizes arbitrarily close to $1/3$, preserving its additive configuration-LP gap up to constant factors. Thus, in the sense of additive configuration LP gap and up to a constant, we confirm the conjecture that 3-partition instances are the hardest bin packing instances. In particular, we obtain an unconditional $Ω(\ls\OPT)$ gap for 3-partition instances. We build on the recent OpenAI construction that uses five items per bin and rules out any constant additive gap.

0.25

Multiplicative Weights for Mixed Block Constraints and Maximum Multicommodity Flow

cs.DS ·2026-11-01 ·Vladimir Kolmogorov
similarity 0.61
Abstract · 15 pages

We study multiplicative-weights (MWU) algorithms for block-separable feasibility problems containing both packing and covering constraints. Each iteration optimizes a weighted linear objective over one block, either chosen uniformly at random or visited in a fixed cyclic order. We show that the cyclic algorithm returns an $O(\varepsilon)$-approximate solution after $O(kρ\varepsilon^{-2}\log m)$ oracle calls where $k$ is the number of blocks and $ρ$ is the width of the oracle. The same holds for the randomized version with high probability. Previously, such bounds were shown when the coupling constraints have the same sign [Radzik'95; Villavicencio-Grigoriadis'96]. These analyses critically depended on monotonicity arguments that are not available in the mixed case. As an application, we obtain a deterministic $(1-\varepsilon)$-approximation for maximum multicommodity flow (M-MCF) using $O(k\varepsilon^{-2}\log m\log(km/\varepsilon))$ approximate single-commodity min-cost-flow calls. For planar graphs, and more generally for graph families admitting a near-linear-time min-cost-flow algorithm, this gives total running time $\widetilde O(km\varepsilon^{-2})$. Compared with the $O(km^{1+o(1)}\varepsilon^{-1})$ algorithm of [Chen-Graur-Sidford'25], this improves the dependence on $m$ for these graph families at the cost of a worse dependence on $\varepsilon$. Finally, we give an exponentiation-free finite-precision implementation of the cyclic algorithm. It represents each internal weight by a logarithmic-bit mantissa and exponent, while every price supplied to the block oracle is rational and has a polynomially bounded common denominator.

0.24