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 6
FPT Isomorphism Test for $F$-Free Tournaments
We show that isomorphism of $F$-free tournaments can be solved in FPT time $f(k) \cdot n^{O(1)}$, where $k$ denotes the size of $F$, and $n$ denotes the size of the input tournaments.On the Offline Version of the Time-Optimal k-Server Problem
We consider the offline problem of parallel relocation of k identical mobile resources.Near-Optimal Online Metric Matching on $Δ$-ary HST
In the online metric matching problem, we have $n$ servers with known locations in some metric space.An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem
For a fixed integer $r\geq4$, the $K_r-e$-free graph sandwich problem asks whether, given graphs $G_1\subseteq G_2$ on the same vertex set, there is an induced-$K_r-e$-free graph $H$ between them.Local Representatives and Shortest Completions for Next-to-Shortest Paths in Directed Graphs
Given a directed graph with positive edge weights and two vertices s,t, a next-to-shortest s-t path is a shortest simple s-t path among those whose length is strictly larger than the shortest-path…Counting and Covering in Nearest-Neighbour Representations of Boolean Functions
We study the number of prototypes needed to represent Boolean functions by nearest-neighbour classification.Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis
Local-to-global techniques for establishing spectral gaps have played a central role in the modern theory of Markov chain mixing times and the theory of high-dimensional expanders.Improved Algorithms for Beck--Fiala with Bounded Sets
We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size.Integrality gap preserving reductions
We propose a framework for the systematic study of integrality gaps of combinatorial optimization problems with respect to a fixed linear programming formulation.Fast FPRAS for the Permanent
We give an FPRAS for the permanent of an $n\times n$ $0/1$ matrix with running time $\widetilde{O}(n^{3.5}\varepsilon^{-2})$.Target-Stratified Fair Range Summaries: Improved Fair $\varepsilon$-Nets and Geometric Hitting Sets
Compact summaries are a key tool for approximate query processing over large datasets.Efficient Algorithms for Subdeterminant Maximization under Partition Matroids
We consider the determinant maximization problem under partition constraints: Given an $n\times n$ PSD matrix A and a partition matroid $M$ on $[n]$, find a base $S$ of $M$ that maximizes…Routing Multiple Agents Below the Sum of Distances
We study Transient Multiagent Pathfinding, a variant of the classical Multi-Agent Pathfinding problem in which a set of agents must be routed without collisions from designated start vertices to…Optimizing Both Checking and Update Costs in Random Walk Search
Random walks are a standard tool for search problems in which a state can be updated locally and tested for being marked.Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with $\|\sum_i s_i H_i\|\le 13\|\sum_i…The Classical Weisfeiler-Leman Algorithm Stabilizes in $O(n)$ Rounds
The classical Weisfeiler-Leman algorithm (also known as the $2$-dimensional Weisfeiler-Leman algorithm) is a simple combinatorial algorithm that was originally designed as a heuristic for the graph…Structural Parameterizations for Eternal Vertex Cover
Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph $G$.A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution
The demand matching problem generalizes both the knapsack problem and the $b$-matching problem.Perfectly Guarding Straits: Exact Algorithms for Weak Visibility Polygons
The Art Gallery Problem (AGP) asks for the fewest guards that see all of a simple polygon.Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231
We give an exact algorithm counting the permutations that avoid a fixed pattern from the following family: the direct sum of an increasing pattern and the pattern 231.