Theory & Algorithms · Computer Science & AI
Discrete Mathematics
The newest papers in Discrete Mathematics that ReadSearch has read, newest first. Each links to its own page, with its authors, date, where it was published and the original.
129 papers, from 4 September 2026 to 5 November 2026: 129 arXiv preprints.
Get the few papers worth your time in Discrete Mathematics every morning.
Follow Discrete Mathematics and ReadSearch reads its new papers each day, then brings you the few worth reading, each with its key finding in a sentence.
Newest papers, page 4
Two Linear Programs are Better than One
The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it.A Fast Greedy Algorithm with a 0.45 Approximation Guarantee for the Airplane Refueling Problem
We study a natural greedy algorithm for the Airplane Refueling Problem (ARP), based on a well-known priority rule.Polynomial directed treewidth forces a large bramble with congestion two
Brambles of constant congestion in directed graphs have interesting structural and algorithmic applications, and it is desirable to find the smallest function $f_c(k)$ such that if a digraph has…An ETH-based quasipolynomial lower bound for Dualization
Dualizing monotone Boolean functions (or equivalently, enumerating minimal transversals in hypergraphs) is a long-standing problem whose output-polynomial-time solvability remains open.Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection
We study two problems: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI).Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
For every fixed proper minor-closed class $\mathscr C$ and every $ε>0$, we give a deterministic LOCAL algorithm that returns a dominating set of size at most $(2a(\mathscr C)+1+ε)γ_f(G)$ on every…The Multiple Unicast Conjecture is False
The undirected multiple-unicast conjecture [LL04] asserts that network coding offers no throughput advantage over multicommodity flow.Fast Almost-Uniform Sampling of Random $k$-SAT Solutions
We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas.On the complexity of the single-move labeled token routing problem
In neutral-atom quantum computers, atoms are moved to target positions along paths of empty positions, and a target position may be reserved for one species of atom.Dijkstra Is NOT Greedy: A Global-to-Local Proof of Correctness
Dijkstra's algorithm is almost universally classified as a canonical greedy algorithm.Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation
We consider a matching problem in which the cost of each edge is a vector with $k$ components.On the Parameterized Complexity of Conflict-Free Edge Cut in Undirected Graphs
In this paper, we study CONFLICT-FREE EDGE CUT (CF-CUT), which is a recently introduced conflict-free version of the MIN-CUT problem that asks to find the minimum number of edges to disconnect a…Hiding a Vertex from the Temporal Explorer: A Lower Bound for Degree-Bounded Temporal Graphs
A temporal graph is a sequence of graphs on a common set of $n$ vertices, its snapshots, one for each time step.An FPRAS for Counting Common Bases of Two Matroids
We design the first polynomial-time algorithms for approximately counting and almost uniformly sampling common bases of two matroids given by their independence oracles.Cores Characterize the One-Pass Streaming Complexity of CSPs
We study the one-pass streaming complexity of CSPs over a fixed finite relation $R$ under three natural objectives: $\textsf{SAT}(R)$, deciding whether all constraints can be satisfied…W[1]-Hardness of Upper Clique Transversal
A clique transversal of a graph is a set of vertices intersecting every maximal clique.Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census
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…New Methods for Constructing Classical and Quantum Codes from Graphs and Matroids
In this paper, we present a method for constructing linear codes derived from book graphs.Grid Theory and Polynomiality in Dynamic Lot-Sizing
Why are some dynamic lot-sizing problems polynomial?Coloring 3-colorable graphs with $O(n^{4/23})$ colors via a Gaussian-cover recursion
We give a randomized polynomial-time algorithm that colors any promised $3$-colorable graph on $n$ vertices with $\smash{O(n^{4/23}) = O(n^{0.17391\ldots})}$ colors, improving on the recent bounds…