CS Paper Radar

Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?

Prashant Chaudhary, Kapil Khandelwal

cs.DM math.OCcs.DS ·submitted 2026-09-23 13:54 UTC · v1

Abstract

One item set evaluated at two capacities $R<D$ produces two concave hulls of optimal value against cardinality. We ask which prescribed pairs arise. Exchange arguments give a necessary system on vertex witnesses, exchange closure (EC), whose scalar consequences form the linear closure. We exhibit a pair satisfying every scalar test that fails EC, so the linear closure is strictly larger already at larger terminal count three; and a globally coherent EC witness admitting no common-size representation although its target pair is realizable. Under a cardinality cap, a four-band classification of one family gives exact thresholds for cap-four realizability, uncapped realizability and the vertex-only capped closure. Pairs whose larger terminal count is at most two are characterized. Under the explicit encoding the decision problem lies in $Σ_2^p$ and is polynomial-time for fixed terminal cardinalities. Exact finite certificates establish agreement of the scalar and witness conditions on six specified domains; sufficiency of uncapped EC remains open.

Comment
28 pages. Code, certificates and verification: https://doi.org/10.5281/zenodo.22823629

Closest papers

Nearest neighbours by meaning across the whole index.

Linear Objective Problems: A Complexity Framework for Bilevel Optimization

cs.CC cs.DMmath.COmath.OC ·2026-11-08 ·Christoph Grüne, James B. Orlin, Lasse Wulf
theory similarity 0.59
Abstract

Many bilevel and robust optimization problems are complete for the second level of the polynomial hierarchy, but such results are usually proven one problem at a time with problem-specific reductions. A recurring obstacle is that the lower level must select an optimal solution rather than merely a feasible one, whereas standard reductions preserve only whether a solution exists, not which solutions are optimal. We introduce linear objective problems (LOP), a framework for optimization problems whose solutions are explicit subsets of a ground set and whose objective is linear in these elements. We define tight solution-embedding reductions, which map the optimal solutions of one problem element by element onto the optimal solutions of another, without having to recognize optimal solutions, which is coNP-hard in general. This gives a notion of LOP-completeness, with Satisfiability as the canonical complete problem, even with unit weights. We show that many classical problems are LOP-complete, including Vertex Cover, Dominating Set, TSP, Knapsack, and Steiner Tree, and we introduce a duality that transfers LOP-completeness between minimization and maximization problems. As our main application, we prove a meta-theorem for min-max regret optimization under interval uncertainty: for every LOP-complete problem, the min-max regret version is $Σ_2^p$-complete. Instead of a separate proof for each nominal problem, it suffices to show that the nominal problem is LOP-complete. This recovers known results for the interval min-max regret versions of Knapsack and Maximum Benefit Set Cover and yields completeness for over 50 further problems.

0.24

On the Support Geometry and Complexity of LABS

cs.CC ·2026-10-19 ·William Cruz-Santos
similarity 0.57
Abstract

LABS are a fundamental combinatorial optimization problem arising in sequence design and statistical physics, yet the formal complexity of the standard fixed-geometry problem remains unresolved. We study how zero-energy complexity changes when support geometry is included as part of the input and then progressively restricted. For unary standard LABS, we establish membership in $\NP$ and a sparsity/Mahaney consequence: Karp NP-hardness would imply $\Ptime=\NP$. For Pair-Set-LABS and Masked-LABS, zero-energy feasibility is polynomial-time decidable when every pair group or masked row has at most three terms and is NP-complete when four terms are allowed. NP-completeness persists when active supports are restricted to contiguous intervals.

0.26

Parameterized Approximation of Max k-Weight CSP: A Dichotomy for Boolean Languages

cs.DS ·2026-10-29 ·Rudranarayan Kar, Souvik Saha, Abhishek Sahu
similarity 0.57
Abstract

We study \textsc{Max $k$-Weight CSP}: maximize the satisfied weight of Boolean constraints with nonnegative rational weights by setting at most $k$ variables to $1$. Each constraint uses at most $d$ distinct variables and a relation from a finite Boolean language $Γ$. This includes \textsc{Partial Vertex Cover}, \textsc{Densest $k$-Subgraph}, bounded-frequency \textsc{Maximum Coverage}, and cardinality-constrained \textsc{Max-SAT}. We completely classify the fixed finite languages admitting an efficient parameterized approximation scheme (EPAS) with parameter $k+d$. Only nonempty relations excluding the all-zero tuple matter. For such a relation, a coordinate is a \emph{unit witness} if the tuple with a single $1$ in that coordinate is accepted, and a \emph{control} otherwise. A relation is \emph{Direct} if setting any selected control to $0$, with all other coordinates unchanged, preserves satisfaction. It is \emph{Rooted} if every satisfying tuple has a selected unit witness such that keeping it, setting all other unit witnesses to $0$, and setting any subset of selected controls to $0$ preserves satisfaction. If all such relations are Direct, or all are Rooted, we give a deterministic $(1-\varepsilon)$-approximation for every rational $\varepsilon\in(0,1)$ in time $2^{O(d+k\log(1+dk/\varepsilon))}\ell_{\mathrm{in}}^{O(1)}$, where $\ell_{\mathrm{in}}$ is the total input length. The algorithms are uniform in $d$ and give an EPAS parameterized by $k+d$ whenever relation membership is polynomial-time decidable. If neither condition holds, no EPAS exists unless $\mathsf{FPT}=\mathsf{W[1]}$, even for unweighted instances where no two constraints involve the same set of variables.

0.25

0/1 integer programming over polytopes of Chvátal rank one is as hard as lattice problems

cs.CC math.OCcs.DM ·2026-10-07 ·Alberto Del Pia
similarity 0.56
Abstract

A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. In 1973, Chvátal asked whether 0/1 integer programs over polytopes of bounded Chvátal rank can be solved in polynomial time. For polyhedra of bounded Chvátal rank, integer feasibility is in NP $\cap$ coNP, so it is unlikely to be NP-hard. We answer Chvátal's question negatively already in its most restricted form: for Chvátal rank one, for integer feasibility, and even for the SAT polytopes of formulas whose clauses have at most three literals. Our answer holds under either of two standard assumptions from lattice-based cryptography. First, a polynomial-time algorithm for integer feasibility on such SAT polytopes of Chvátal rank one would solve bounded distance decoding with polynomial factors in deterministic polynomial time, contradicting the conjectured hardness of approximating lattice problems within polynomial factors. Second, assuming the hardness of learning with errors, an average-case analog of bounded distance decoding, the problem is also hard on average, for a polynomial-time samplable distribution of formulas. This also gives negative answers to related questions of Cornuéjols, Lee, and Li. We first prove these results for parallelepipeds, where they rest on an elementary sufficient condition: a polyhedron has Chvátal rank at most one if its width is less than one along every row of some unimodular matrix. For our parallelepipeds, such a matrix exists but is hard to find. For SAT polytopes, we represent candidate lattice vectors by their residues modulo small integers, and binary arithmetic on additional 0/1 variables checks that these vectors lie in the lattice.

0.27

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

Approximating the Chvátal--Gomory Closure of Capacity-Bounded Min-Closed Systems

cs.DS ·2026-09-28 ·Stefano Huber, Monaldo Mastrolilli
publishedtheory similarity 0.55
Abstract · 19 pages, a short version of this paper appears in the proceedings of ISAAC 2026

Optimizing over the {0, 1/2} rank-1 Chvàtal-Gomory (CG) closure of a binary integer linear program is NP-hard. While polynomial-time approximation schemes (PTAS) are established for monotone packing and covering formulations, extending these guarantees to mixed-sign variants remains an open challenge. In this paper, we study the approximability of the CG closure for k-slack bounded (capacity-bounded) min-closed systems, a generalized packing formulation with mixed-sign constraints that extends weighted Boolean Horn logic. In these systems, a constant upper bound $k \ge 1$ bounds the ratio between the negative penalty coefficient $q$ and the right-hand side capacity $b$ of every constraint, enforcing $q \le k \cdot b$. We prove that a constant-degree sum-of-squares relaxation yields a PTAS for maximizing linear objectives over the first CG closure generated by multipliers in $\{0\}\cup[\tfrac1f,1]$, for any constant integer $f \ge 2$. This closure is contained in the {0, 1/2} rank-1 CG closure.Optimizing over the {0, 1/2} rank-1 CG closure of a binary integer linear program is NP-hard. While PTASes are established for monotone packing and covering formulations, extending these guarantees to mixed-sign variants remains an open challenge. In this paper, we study the approximability of the CG closure for \emph{$k$-slack bounded (capacity-bounded) min-closed systems}, a generalized packing formulation with mixed-sign constraints that extends weighted Boolean Horn logic. In these systems, a constant upper bound $k \ge 1$ bounds the ratio between the negative penalty coefficient $q$ and the right-hand side capacity $b$ of every constraint, enforcing $q \le k \cdot b$. We prove that a constant-degree sum-of-squares relaxation yields a PTAS for maximizing linear objectives over the first CG closure generated by multipliers in $\{0\}\cup[\tfrac1f,1]$, for any constant integer $f \ge 2$.

0.61

Running-Time Lower Bounds under FPT $\neq$ W[1]

cs.DS cs.CC ·2026-11-19 ·Hendrik Molter
similarity 0.55
Abstract

We revisit running-time lower bounds historically based on the Exponential Time Hypothesis. Our case study asks how much of their quantitative content can be recovered under the assumption FPT $\neq$ W[1]. The reductions encode the choice of a clique in few bits and control the target parameter in terms of that encoding. This makes a sufficiently fast algorithm for the target problem yield a fixed-parameter algorithm for deciding whether a graph has a clique of the requested size. We obtain twelve lower bounds for deterministic algorithms across graph, string, and integer feasibility problems, including bounds that hold under structural restrictions. In several cases the same function of the parameter appears in the exponent as in the historical bound, with the additional requirement that the cutoff for any prescribed saving in the exponent be computable.

0.14

Fair Division of Graphs: Beyond Traceability

cs.GT cs.DMmath.CO ·2026-08-30 ·Nicolas Bousquet, Frank Connor, Agnès Totschnig, Sébastien Zeitoun
similarity 0.55
Abstract

In this paper, we study fair division problems in which resources are structured as graphs and agents must receive connected bundles. This connectivity requirement fundamentally alters the problem, making it significantly more challenging than its classical counterpart. We focus on the fairness notion of $\mathrm{EF1}_{\mathrm{outer}}$, where envy can be eliminated by removing at most one vertex whose deletion does not disconnect the bundle -- a critical constraint for applications such as land division and network allocation. Our first result extends prior work by establishing the existence of $\mathrm{EF1}_{\mathrm{outer}}$ allocations for an infinite family of non-traceable graphs (that is, graphs that do not admit a Hamiltonian path), answering a central open question and generalizing Bilò et al.'s result for traceable graphs. We then make progress on a conjecture concerning the $\mathrm{EF1}_{\mathrm{outer}}$ spectrum of trees due to Chen and Zwicker. Finally, we complement our structural results with algorithmic insights, showing that deciding the existence of an $\mathrm{EF1}_{\mathrm{outer}}$ allocation is NP-complete even for binary additive valuations, thereby resolving an open complexity question. Taken together, our results deepen the connection between graph theory and fair division, and offer new tools for studying fairness in structured resource environments.

0.06