Papers for

combinatorial optimization engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Random k-sat solutions connect by single flips below key density thresholds

Single-Variable Connectivity in Random $k$-SAT

Abstract: We resolve longstanding questions about connectivity, reconstruction,and looseness in random $k$-SAT, for sufficiently large fixed $k$ as the number $n$ of variables tends to infinity. $\textbf{Single-variable connectivity up to reconstruction.}$ At clause densities up to \[\frac{2^k}{k}\bigl(\ln k+\ln\ln k+γ_*-o_k(1)\bigr),\] a polynomial-time algorithm joins a typical pair of satisfying assignments with high probability, using $O_k(n)$ single-variable flips that preserve satisfiability. Here $γ_*\approx0.871$ arises from a refined tree-reconstruction analysis. $\textbf{Settling the reconstruction threshold.}$ Building on the tools developed for connectivity, we determine the clustering threshold defined by the reconstruction criterion to be \[\frac{2^k}{k}\bigl(\ln k+\ln\ln k+γ_*+o_k(1)\bigr),\] below the classical cavity prediction with constant term $1+O(\ln\ln k/\ln k)$. $\textbf{Shattering before rigidity.}$ We locate the looseness--rigidity transition at a higher density, matching the classical cavity prediction for clustering: \[\frac{2^k}{k} \left(\ln k+\ln\ln k+1+Θ\left(\frac{\ln\ln k}{\ln k}\right)\right).\] Below the transition, we establish a stronger form of looseness: any variable of a typical solution can be reversed by logarithmically many single-variable flips that preserve satisfiability. Above it, reversing most variables of a typical solution requires changing linearly many variables (rigidity). Yet throughout an interval between reconstruction and rigidity, the solution space already splits into groups of exponentially small relative size separated by linear Hamming distance and linear energy barriers (shattering), while logarithmic looseness persists.

Wed 4 NovData Structures and AlgorithmsDiscrete Mathematics
The gist
The paper studies how solutions to a complex logical puzzle called random k-SAT are connected and change as you adjust the number of rules. The authors show that up to a certain point, you can move between solutions by flipping one variable at a time in a way that always keeps the puzzle solvable. They identify precise mathematical thresholds where the solution space changes structure—from connected, to clustered, to rigid where flipping variables becomes hard. This deepens understanding of the puzzle’s structure and transitions as its difficulty increases.
Open → 2611.05981v1

Polynomial time algorithm estimates antiferromagnetic Ising model partition function

On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum

Abstract: We give the first polynomial-time algorithm to estimate the partition function of the antiferromagnetic Ising model on the uniformly random $d$-regular graph to arbitrarily high accuracy for all inverse temperatures up to the Kesten-Stigum threshold. This is the entire regime in which the model is "replica symmetric," and is conjectured to be optimal for polynomial-time counting and sampling. To achieve our algorithmic result, we establish the absence of Fisher zeros for the partition function in a constant-width strip around the interval from $0$ up to the Kesten-Stigum threshold, with high probability over the randomness of the input graph. AI Disclosure: The overarching vision and proof architecture were developed solely by the authors without AI input. GPT 5.5 Pro was used, with extensive guidance from the authors, for only a few minor technical aspects of the proof. The authors independently verified correctness and wrote everything by hand. We take full responsibility for its contents. A more detailed statement can be found in Section 1.2.

Thu 29 OctData Structures and Algorithms
The gist
The paper addresses how to accurately estimate a key number called the partition function in a complex model used to study things like magnetism on random networks. The authors created an efficient algorithm that works well up to a certain threshold, known as the Kesten-Stigum threshold, which is believed to be the best possible limit for such computations. They proved that certain problematic zeros, which could make the calculation hard, do not appear near this range, making the algorithm reliable. This work helps understand where efficient estimation is feasible in these complicated systems.
Open → 2610.40598v1

Hierarchical cooperative networks improve exploration in generative models

Hierarchical Cooperative GFlowNets

Abstract: Generative Flow Networks (GFlowNets) are trained to sample objects from compositional spaces with probability proportional to a reward function, but ineffective exploration can cause learned samplers to concentrate on a few high-reward regions. An intuitive remedy is to train multiple GFlowNets independently in parallel and combine their samples. However, this does not prevent multiple models from collapsing onto the same high-reward areas, leaving large regions of the state space unexplored. With this in mind, we propose Hierarchical Cooperative GFlowNets (HCG), an approach that dynamically partitions the search space to coordinate discovery without relying on hand-crafted boundaries. HCG imposes an ordering in which the highest-ranked model may explore the entire space, while lower-ranked models are progressively pushed toward regions not covered by higher-ranked ones. We provide a theoretical characterization of how specific learning objectives can shift probability mass away from designated areas, instantiating this mechanism within our architecture. A shared classifier coordinates the hierarchy by partitioning the search space, keeping the GFlowNets independently parameterized and enabling asynchronous training. Furthermore, we derive a normalizer-weighted aggregation rule for the ensemble and prove that it recovers the target reward-proportional distribution under the stated assumptions. Finally, experiments across multimodal distributions, sequence generation, combinatorial optimization, and biological sequence design show that HCG improves mode coverage and target approximation, translating increases in the number of coordinated samplers into broader, complementary exploration.

Sun 25 OctMachine LearningArtificial Intelligence
The gist
Sampling diverse and interesting examples from complex spaces is hard because models tend to focus only on a few popular areas. The authors propose Hierarchical Cooperative GFlowNets, which let multiple models work together by dividing the search space dynamically. Higher-ranked models explore broadly while others focus on less-covered regions, encouraging diversity. Their method better covers all possibilities and produces samples that match the desired probabilities across many tasks.
Open → 2610.33968v1

Matroid base optimization enables faster group label constraint solutions

Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases

Abstract: Let $M$ be a matroid, let $\ell:E(M)\to G$ be a labeling of its elements by an abelian group, and let $F\subseteq G$ be finite. A base is $F$-avoiding if the label sum of its elements is not in $F$. We prove that, for arbitrary costs, a min-cost $F$-avoiding base can be obtained from any min-cost base using at most $|F|$ exchanges. This resolves the weighted proximity conjecture by Hörsch, Imolay, Mizutani, Oki, and Schwarcz. Our main technical tool is to replace the assumption of Schrijver--Seymour Conjecture in Liu and Xu's earlier work with Kemperman--Scherk Theorem. The proximity theorem combined with approaches in earlier work gives an FPT algorithm that finds a min-cost $F$-avoiding base parameterized by $|G|$. We additionally give an FPT algorithm parameterized by $|F|$, answering a question of Hörsch et al.

Fri 23 OctData Structures and Algorithms
The gist
Matroids are mathematical objects that describe structures with a notion of independence, like networks or graphs. This paper looks at ways to find the least costly group of elements (a "base") whose combined labels, from a group, avoid certain forbidden sums. The authors prove that only a limited number of swaps are needed to move from any cheapest base to one that avoids these sums and provide algorithms that quickly find such solutions when the size of the group or forbidden sets is small. This advances understanding and tools for optimizing with complex group-label constraints.
Open → 2610.32798v1

Computing the nucleon allocation efficiently in matching games and variants

Computing the Nucleon of Matching Games

Abstract: The nucleon is the multiplicative counterpart of the nucleolus: it lexicographically maximizes the fraction of its stand-alone value that each coalition receives. We study exact nucleon computation in matching games and in two extensions: $b$-matching games, in which players may have several partners, and partitioned matching games, in which one player may own several vertices. We resolve three open problems from a recent survey. For ordinary matching games with nonnegative rational weights, we give a polynomial-time combinatorial algorithm using maximum-weight matching, shortest paths, and minimum-cost flow, ; it returns both a nucleon allocation and a compact description of the full nucleon. In contrast, computing any nucleon allocation is NP-hard for unit-weight $b$-matching games with capacities at most three and for unit-weight partitioned matching games of width at most three. Finally, for the unresolved capacity-two case, we show that exact nucleon computation is polynomial-time Turing reducible to SHORTEST NON-ZERO CYCLE.

Wed 21 OctComputer Science and Game Theory
The gist
Certain kinds of games called matching games involve players forming partnerships to share rewards. The authors study a way of fairly dividing rewards called the nucleon, which balances how much value each group of players gets compared to what they could gain alone. They develop a practical algorithm to find nucleon allocations quickly for basic matching games but show that it is very hard (NP-hard) to do so for more complex versions. For a specific intermediate case, they connect the problem to finding special cycles in graphs, providing a new perspective.
Open → 2610.29731v1

Approximate sampler algorithm for complex macdonald processes

A Randomized Approximation Algorithm for Doubly Free-Boundary Macdonald Processes

Abstract: We construct an approximate sampler for finite doubly free-boundary Macdonald rail-yard processes with Macdonald, boundary, and edge parameters in $(0,1)$. The construction allows arbitrary finite sequences of additions and removals of horizontal or vertical strips and all four boundary types. It reverses a finite commutation--reflection history from a partition sequence whose entries are equal, with the common partition weighted by both boundaries. We derive local reconstruction kernels from the skew Cauchy, Littlewood, and branching identities. Bulk and boundary updates combine integer increments with conditional shape sampling at a prescribed size; same-sign swaps use finite conditional resampling. For $K$ reflection periods and an initial partition-size cutoff $M$, the algorithm terminates almost surely and samples the resulting approximating law exactly. We prove total variation convergence to the target process as $K,M\to\infty$ and give explicit bounds for both truncation errors, decaying geometrically in the cutoffs for fixed input parameters. Under fixed parameter bounds, we also bound the expected operation count of direct enumeration in a unit-cost model. We further construct an exact rejection sampler for the initial partition law without a size cutoff or evaluation of its normalizing constant. Using this sampler removes the size-truncation error, leaving only the error from the finite reflection history.

Tue 13 OctDiscrete MathematicsData Structures and Algorithms
The gist
This paper addresses how to efficiently generate random samples from a complicated mathematical model called doubly free-boundary Macdonald processes. The authors develop an algorithm that can approximate this sampling by gradually refining parameters and guarantees almost sure termination with exact sampling of the approximation. They provide mathematical proofs showing the method converges to the true process and also explain how to remove certain approximation errors with an exact initial sampler. This work helps handle complex partition structures with various boundary conditions in a controlled and computable way.
Open → 2610.18698v1

Stable matching instances have unique prime factorizations and exact counts

Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census

Abstract: Every balanced instance of the stable marriage problem with strict complete preferences has a unique finest partition into prime blocks, and that single partition simultaneously factors three different structures: the reachable execution digraph as a Cartesian product, the proposal-prefix antimatroid as a direct sum, and the stable-matching lattice as a direct product. The converse fails, and fails at every size from two on: two explicit families share the identical Boolean-cube execution while one is maximally decomposable with a single stable matching and the other is prime with n. Uniqueness yields an exact census, a recursion counting the prime instances at every size, under which exactly 88,478,208 of the 110,075,314,176 profiles with four agents on each side are decomposable and the decomposable fraction is asymptotically n! / n^(2n). The blocks are characterised as the square components of the mutual-rank filtration, so the partition is computable in polynomial time and the factorisation is a tool rather than only a fact.

Sun 4 OctData Structures and Algorithms
The gist
Finding stable matches is a classic math problem about pairing groups fairly. The authors show that any balanced instance can be uniquely broken down into fundamental parts called prime blocks. These blocks reveal deep connections between different ways to look at the problem's structure. They also count exactly how many cases can be broken down this way, showing most are decomposable, and provide a way to find this breakdown efficiently.
Open → 2610.05617v1

Odd cycle transversal problem solved faster for certain graph classes

Odd Cycle Transversal on $H$-free graphs

Abstract: \textsc{Odd Cycle Transversal} is a classic $\mathsf{NP}$-hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite, or equivalently, a maximum-weight induced bipartite subgraph. We show that \textsc{Odd Cycle Transversal} is quasi-polynomial-time solvable on $kP_4$-free graphs, for every fixed $k \in \mathbb{N}$. In fact, we provide an $n^{O_k(\log n)}$-time algorithm for the more general \textsc{Max-Weight List $2$-Colorable Induced Subgraph}, where the notation $O_{k}(\cdot)$ hides factors depending on $k$. Paired with known results from the literature, this allows us to obtain a complete complexity dichotomy for these two problems on $H$-free graphs into cases solvable in quasi-polynomial time and cases which are $\mathsf{NP}$-hard, in particular resolving an open problem of Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024]. Our algorithms are based on a new structural tool that may be of independent interest. We introduce the notion of $H$-amiable family and show that, for every fixed graph $H$ without isolated vertices and every fixed $k\ge2$, every $kH$-free graph admits an $H$-amiable family of quasi-polynomial size that can be constructed in quasi-polynomial time. Besides yielding the aforementioned algorithms, this result gives, for every fixed connected graph $H$ and every fixed $k\ge2$, a reduction from \textsc{Max-Weight Independent Set} on $kH$-free graphs to the same problem on $H$-free graphs with $n^{O_{H,k}(\log n)}$ overhead. In this setting, it improves the $n^{O_{H,k}(\log^3 n)}$ overhead obtained by specializing the general reduction of Gartland and Lokshtanov [FOCS 2020].

Fri 25 SeptData Structures and AlgorithmsDiscrete Mathematics
The gist
The odd cycle transversal problem involves finding a smallest set of points in a network to remove so the network has no odd loops, making it easier to analyze. This problem is usually hard to solve, but the authors develop a faster algorithm for networks that avoid certain repeated patterns. Their approach also improves ways to find large independent groups of points in these networks. They achieve this by introducing a new structural concept called an "H-amiable family," which helps break down complex networks into simpler parts.
Open → 2609.30900v1

Graphs with large odd cycles need minimum connections for small triangle-free mappings

Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth

Abstract: We determine the asymmetric homomorphism threshold from graphs of odd girth at least $7$ to triangle-free graphs, showing that $δ_{\mathrm{hom}}(\{C_3,C_5\},\{C_3\})=\frac{1}{9}$. Equivalently, for every $\varepsilon>0$, every $n$-vertex graph of odd girth at least $7$ and minimum degree at least $(1/9+\varepsilon)n$ admits a homomorphism to a triangle-free graph of size bounded by a function of $\varepsilon$, while there exist graphs of odd girth at least $7$ and minimum degree at least $(1/9-\varepsilon)n$ for which no such bounded-size triangle-free homomorphic image exists. More generally, for every $t\geq 3$, we prove $δ_{\mathrm{hom}}(\{C_3,C_5\},\{K_t\})=\frac{1}{3t}$. In particular, for every proper monotone class $\mathcal C$ of graphs, the threshold for graphs of odd girth at least $7$ to admit a homomorphism to a bounded-size graph in $\mathcal C$ is positive. We further extend this phenomenon to arbitrary odd girth: for every $k\geq 2$ and every proper monotone subclass $\mathcal C$ of the class of graphs of odd girth at least $2k-1$, the threshold for graphs of odd girth at least $2k+3$ to admit a homomorphism to a bounded-size graph in $\mathcal C$ is positive. These results disprove conjectures of Gishboliner, Hurley and Wigderson and exhibit a sharp contrast with the corresponding zero chromatic-threshold results. Our lower-bound constructions are based on high-dimensional Borsuk graphs, while the matching upper bounds use regularity arguments to recover the structure underlying these constructions.

Mon 21 SeptDiscrete Mathematics
The gist
The authors studied special large graphs that avoid certain small odd cycles and explored how connected these graphs must be to simplify them into triangle-free graphs with a limited size. They found exact numbers that show when this simplification is possible and when it is not. Their results disprove previous guesses and reveal surprising differences compared to related graph coloring problems. The work uses advanced mathematical tools, including geometric constructions and combinatorial methods, to prove these properties.
Open → 2609.25390v1

Universal sets approximate best solutions for submodular and XOS functions

Universal set families for maximization of nonnegative submodular and XOS functions

Abstract: We consider the question of designing a universal family of sets $F \subset 2^{[n]}$ such that for any function $f:2^{[n]} \to R_{\geq 0}$ in a certain class, we have $$\max_{S \in F} f(S) \geq c(n) \cdot \max_{S \subset [n]} f(S).$$ We prove that there is a family of subpolynomial size such that for any nonnegative submodular function, $c(n) = Ω(\frac{\log \log n}{\log n})$, and there is a family of logarithmic size such that $c(n) = Ω(\frac{1}{\log n})$. We also prove that pairwise independence (which achieves a constant factor for graph cut functions), or even $k$-wise independence, does not imply a bound better than $O(\frac{1}{\sqrt{\log n}})$ for submodular functions. On the other hand, we prove that for any polynomially representable subclass of nonnegative submodular functions (such as the matroid connectivity functions for matroid representable over $F_q$), a constant-factor universal family of polynomial size always exists. For absolute XOS functions (a class that we introduce, in the form $f(S) = \max_i |\sum_{j \in S} w_{ij} + c_i|$ where $w_{ij}, c_i \in R$), we design a family of polynomial size such that $c(n) \geq \sqrt{\frac{\log n}{n}}$, and prove that there is no polynomial-size family achieving a factor better than $O(\sqrt{\frac{\log n}{n}})$.

Thu 17 SeptData Structures and Algorithms
The gist
Finding the best subset that maximizes certain functions can be very challenging. The authors study how to create a small collection of universal sets that work well for a wide range of functions, guaranteeing a fraction of the best possible value. They show this collection can be very small for specific function types and prove limits on how good these universal families can get. Their work also introduces a new type of function and finds matching upper and lower bounds for approximations by polynomial-sized families.
Open → 2609.19528v1

Fast methods find multiple largest common sets in matroids with fewer queries

Subquadratic-Query Algorithms for Finding Another Maximum Matroid Intersection

Abstract: Let $\mathcal{M}_1,\mathcal{M}_2$ be two matroids on a common ground set $V$, given by independence oracles, and let $S$ be a maximum-cardinality common independent set. We study the problem of deciding whether there exists another maximum common independent set $T\ne S$, and of outputting one when it exists. Writing $n=|V|$ and $r=|S|$, we give a Las Vegas algorithm using $\tilde O(n\sqrt r)$ expected independence queries and a deterministic algorithm using $\tilde O(nr^{2/3})$ queries. As an application, all maximum common independent sets can be enumerated with at most two another-solution calls between consecutive outputs and after the last output; if there are $L$ solutions, exactly $2L-1$ such calls are made. Neither algorithm constructs the exchange graph. Instead, they perform Kahn-style source peeling through two deletion-only data structures. One side uses the heavy/light categorization of Blikstad, van den Brand, Mukhopadhyay, and Nanongkai. For the opposite side, where no transposed oracle is available, we give a collective randomized classifier and a deterministic capacity-saturation certificate.

Wed 16 SeptData Structures and Algorithms
The gist
Imagine you have two systems each with rules about which items can be chosen, and you want to find the largest set of items that fit both systems' rules. After finding one largest set, the authors look for another different largest set, which is usually very hard. They created new algorithms that can find or confirm another largest set faster than before by making fewer checks to the rules. Their methods also let you list all the largest sets one after the other efficiently, without building large complex structures.
Open → 2609.18199v1

Nullstellensatz degree bounds affect graph coloring complexity

Nullstellensatz degree under Hajós joins and vertex identifications

Abstract: We study the minimum coefficient degree $N_{k,\F}(G)$ of a Nullstellensatz certificate for Bayer's $k$-coloring equations, where the characteristic of $\F$ does not divide $k$. If $J$ is a \HJ\ join of non-$k$-colorable graphs $G,H$ and $m=\max\{N_{k,\F}(G),N_{k,\F}(H)\}$, then $N_{k,\F}(J)\leq m+k$. When deletion of the selected edge makes each input $k$-colorable, we also have $N_{k,\F}(J)\geq m$; the degree congruence then gives $N_{k,\F}(J)\in\{m,m+k\}$. This partially answers a question of Li, Lowenstein, and Omar. For three-coloring over $\F_2$, we construct an infinite $4$-critical family of exact degree seven, attaining the bound at input degree four. In contrast, every graph constructed from $K_4$ solely by \HJ\ joins has degree $O(\log n)$ and a certificate with polynomially many terms: joins preserve treewidth at most three, and balanced separators yield low-degree certificates. Additional vertex identifications are excluded from this obstruction. We classify all single identifications of the $25$-vertex base graph; exactly $36$ preserve degree seven, producing $24$-vertex $4$-critical graphs of treewidth four. A compressed self-join at adjacent true twins prevents degree loss and gives a repeatable rule adding four vertices per round. The rule does not establish degree amplification or preservation of criticality. Exact witnesses and standalone verification programs accompany the finite results.

Mon 14 SeptComputational Complexity
The gist
The paper studies how complex it is to prove that certain graphs cannot be colored with a set number of colors, using a mathematical tool called the Nullstellensatz. The authors find limits on this complexity when combining graphs in specific ways called Hajós joins and vertex identifications. They show examples of graphs that reach these limits and classify particular operations that preserve this complexity measure. Their results help understand the difficulty of coloring graphs and provide exact certificates for these proofs.
Open → 2609.14865v1

Tournaments that cannot be represented by five voters orders found

Tournaments not inducible by five voters

Abstract: A tournament T is k-inducible if there are k linear orders on its vertex set such that, for every arc $i \to j$ of T, a majority of the orders rank i above j. For odd k, let N(k) be the least order at which some tournament is not k-inducible. Only N(3) = 8 is known exactly; for N(5) the best bounds were $12 \le N(5) \le 38$, from our previous paper [2], which also gave the first explicit example of moderate order, the Paley tournament $P_{43}$. Results. A bespoke search algorithm improves both ends: $13 \le N(5) \le 23$. The upper bound comes from proving that $P_{23}$ is not 5-inducible, the case Bachmeier et al. [1] reported they could not decide, their SAT solver not having terminated within a cumulative six weeks; ours takes 22 hours on one laptop. The lower bound comes from an analysis at order 12. We also show that $P_{31}$ is not 5-inducible, while $P_{19}$ is 5-inducible but not with unit margin, that is, not by a profile in which every arc is carried by exactly three voters against two. Both $P_{19}$ and $P_{23}$ are arc-critical for their respective properties, whereas $P_{31}$ and $P_{43}$ are not vertex-critical: deleting a vertex leaves a tournament that is still not 5-inducible. Method. The search places one vertex at a time, always choosing the vertex with the fewest options left, and propagates the consequences. Together with the automorphisms of the tournament, this decides on a single laptop instances that neither integer programming nor a general-purpose SAT solver can settle. The refutations for $P_{19}$ and $P_{23}$ are certified as well: the search is split into independent subproblems, a SAT solver emits a machine-checkable proof for each, and a separate program rechecks every proof. All results, subject to two human-checked lemmas, are reproducible from https://github.com/Leonardini/TournamentsBeyond5Voters.

Sat 12 SeptDiscrete Mathematics
The gist
The paper explores a type of mathematical structure called a tournament, which can sometimes be represented by a group of voters ranking options in order. When five voters rank these options, some tournaments cannot be matched exactly by their majority preferences. The authors improved the known smallest size of such a tournament and provided new examples using clever search algorithms and proof techniques. They also created verified computer proofs to confirm these results, making them reliable and reproducible.
Open → 2609.13924v1