CS Paper Radar

A Polymatroidal Perspective on Random Contraction

Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu

cs.DS ·submitted 2026-09-03 22:19 UTC · v1

Abstract

Karger's elegant random contraction algorithm for finding a global mincut in a graph has been highly influential. More recent work has obtained several different (nonuniform) random contraction algorithms for mincut in hypergraphs and hedgegraphs. Motivated by the conceptual goal of understanding these algorithms in a unified fashion, we study random contraction algorithms for finding a minimum quotient of a polymatroid. We introduce the notion of quotient-bounded polymatroids and show that several existing results can be derived and understood under a common algorithmic framework for quotient-bounded polymatroids.

Closest papers

Nearest neighbours by meaning across the whole index.

Incremental Directed Minimum Cut by Dynamizing Gabow's Algorithm

cs.DS ·2026-08-17 ·Thatchaphol Saranurak, Kaiyang Xie, Zhaienhe Zhou
similarity 0.58
Abstract

We give the first incremental algorithm for directed global minimum cut. Given a directed graph with $n$ vertices undergoing $m$ edge insertions, our deterministic algorithm explicitly maintains a global minimum cut or certifies that its value is at least $k$ in $O(km\log n)$ total update time. Prior work required either that $k\le2$ or that the graph is undirected. Our algorithm is a strict incremental extension of Gabow's state-of-the-art static algorithm (JCSS 1995), with no asymptotic loss in running time over the entire insertion sequence.

0.51

Derandomizing Karger's Contraction Algorithm for Matroids

cs.DS cs.DMmath.CO ·2026-08-17 ·Yu Cong, Chao Xu, Yajie Zhao
theory similarity 0.57
Abstract

Karger's randomized contraction algorithm finds a minimum-weight cocircuit of a matroid whenever the cogirth-density ratio is bounded. We prove that the same hypothesis yields a deterministic algorithm with the same exponent. If every contraction minor of rank at least $r_0$ of a matroid $M$ has cogirth-density ratio at most $c$, then a minimum-weight cocircuit of $M$ is computable deterministically in $m^{O(r_0)} n^{O(c)}$ time when the contraction minors of bounded rank have at most $m$ parallel classes, by an algorithm that knows neither $r_0$ nor $c$. As a consequence, we give a deterministic algorithm computing the cogirth of rank-$p$ perturbed graphic matroids in $2^{O(p^2)} n^{O(1)}$ time, fixed-parameter tractable in $p$, settling the cogirth side of a question of Geelen and Kapadia (2018). The extensions of the contraction method carry over deterministically: enumerating all near-minimum 1-cocycles, computing a minimum-weight $k$-cocycle, and computing the Pareto frontier under several positive criteria.

0.35

Graph Matching in Random Geometric Graphs I: Efficient Algorithms

cs.DS math.PRmath.ST ·2026-10-12 ·Dong Huang, Ankang Jiao, Shuangping Li, Zhangsong Li
hot direction similarity 0.57
Abstract · 62 pages, 4 figures

We study the recovery of the hidden vertex correspondence between two correlated dense random geometric graphs. Each graph is generated from $n$ latent unit vectors in $\mathbb R^d$; the vectors $u_i^A$ and $u_i^B$ of corresponding vertices satisfy $\langle u_i^A,u_i^B\rangle=ρ$, and the vertex labels of the second graph are permuted by an unknown permutation $π$. For every fixed correlation $ρ\in(0,1]$ and every edge density bounded away from zero and one, we give a randomized polynomial time algorithm that recovers $π$ exactly with probability tending to one whenever $d\ge(\log n)^L$, where $L$ depends only on the correlation and the density bounds. The algorithm assigns to each vertex a signature formed by counting decorated paths with a constant number of seeds. The number of such seeded templates grows exponentially with the path length, with an arbitrarily large constant base, so the resulting statistics amplify an arbitrarily small constant correlation. We control the dependencies created by the latent geometry in two ways: when $d$ is larger than $n/(\log n)^{L_0}$ for a suitable constant $L_0$, by comparing local moments with those of correlated Erdős--Rényi graphs; for smaller $d$, by spectral estimation of the latent geometry combined with a harmonic correction. We also provide low-degree evidence for a tradeoff between the correlation and the computational cost.

0.36

A Shortest Augmenting Path Algorithm for Linear Matroid Parity

cs.DS ·2026-10-02 ·Kou Hamada, Satoru Iwata
similarity 0.56
Abstract

The matroid parity problem generalizes both graph matching and matroid intersection. Although the general version is intractable, Lovász (1981) developed a polynomial-time algorithm for the linear matroid parity problem, assuming the availability of matrix representations. Subsequently, Gabow and Stallmann (1986) presented an augmenting path algorithm, which has long been recognized as one of the fastest deterministic algorithms. Since shortest augmenting paths improved algorithms for graph matching (Micali & Vazirani, 1980) and linear matroid intersection (Cunningham, 1986), extending these techniques to linear matroid parity appears to be a natural progression. However, such an algorithm has remained elusive for four decades. We present the first shortest augmenting path algorithm for linear matroid parity. Our approach synthesizes the augmenting path algorithm of Gabow and Stallmann with the synchronized blossom formation of Micali and Vazirani, whose correctness was recently proven by Vazirani (2024). Our key technical contributions are threefold: (i) a linear-algebraic argument that bounds the lengths of shortest augmenting paths for linear matroid parity, which generalizes Cunningham's bound for linear matroid intersection; (ii) an a priori characterization of shortest search paths through lower bounds on their lengths; and (iii) an extension of the structural properties for graph matching established by Izumi, Kitamura, and Yamaguchi (2025) to the linear matroid parity setting. Our algorithm deterministically solves the linear matroid parity problem in ${\rm O}(nr^2\log r)$ time, where $n$ is the ground set size and $r$ is the matroid rank. By incorporating fast matrix multiplication, this complexity can be further reduced to ${\rm O}(nr^2)$. These results improve upon the long-standing deterministic bounds of ${\rm O}(nr^3)$ and ${\rm O}(nr^ω)$.

0.13

Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness

cs.DS ·2026-11-03 ·Hector Tierno, Shuang Yang
theory similarity 0.56
Abstract

The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give $n^{1/2+o(1)}$-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an $n^{2/15-\varepsilon}$-approximation in $\widetilde{O}(m+n)$ time for every fixed $\varepsilon\in(0,2/15)$, establishing the necessity of polynomial loss for nearly-linear time algorithms.

0.25

Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\geq 2$

cs.DM cs.DSmath.CO ·2026-10-30 ·Yanyu Chen, Yu Chen
theory similarity 0.55
Abstract

Given a simple undirected graph on $n$ vertices, random $k$-out sampling forms a spanning subgraph by having each vertex independently choose $k$ incident edges uniformly with replacement. We prove that, for every integer $k\geq2$, the expected number of original edges joining distinct sampled components is $O(n/k)$. This resolves the conjecture of Holm, King, Thorup, Zamir, and Zwick in its full range, improving their logarithmic sampling requirement to the optimal threshold of two choices per vertex. The bound fails for $k=1$, and the dependence $O(n/k)$ is tight up to constant factors. Our result holds with replacement and consequently also without replacement. In particular, this implies that contracting just two independent local choices per vertex suffices to reduce an arbitrary simple graph to a quotient with $O(n)$ edges in expectation, which is crucial in reducing the instance size for many contraction-based algorithms. Our proof uses switching arguments to relate intercomponent edges to bridges and a degree-weighted component potential, whose expectation we also bound with a switching argument.

0.26

Matroid Connectedness and Component Decomposition: Breaking the Quadratic Barrier

cs.DM ·2026-11-17 ·Manuel Aprile, Roberto Ronco
theory similarity 0.55
Abstract

Deciding whether a matroid is connected and computing its connected components are two fundamental algorithmic problems in matroid theory. Since the 1970s, the best known algorithms for both problems have used $O(n^2)$ independence queries on an $n$-element ground set. Our main contribution is to break this quadratic barrier: we give a deterministic algorithm that computes all connected components of a matroid on $n$ elements with $O(n \log{n})$ independence queries. Our algorithm for component decomposition combines fundamental basis exchanges with a disjoint-set union data structure, avoiding the explicit construction of the fundamental graph. Moreover, we show that our algorithm is asymptotically optimal by giving a lower bound based on a simple information-theoretic argument: any (deterministic or bounded-error randomized) algorithm to compute connected components needs $Ω(n \log{n})$ independence queries. Then, we turn to the query complexity of deciding whether a matroid is connected. For this problem, we present an algorithm that uses $O(nh)$ independence queries, where $h \ge 1$ bounds the size of any chain of nonempty proper cyclic flats. The algorithm achieves asymptotically optimal linear query complexity on elementary split matroids, that include all paving matroids, and on arbitrary direct sums of uniform matroids.

0.15

EPPA for Reducts of the Random Graph

cs.DM math.COmath.LO ·2026-10-29 ·Sofia Brenner, Jan Hubička, Matěj Konečný
theory similarity 0.55
Abstract

We prove that finite two-graphs have coherent EPPA and that neither graphs modulo global complementation nor two-graphs modulo global complementation have EPPA. This completes the classification of EPPA and coherent EPPA for the reducts of the random graph, answering a question and confirming a conjecture of Evans, Hubička, Konečný and Nešetřil.

0.57