Derandomizing Karger's Contraction Algorithm for Matroids
2026-08-17 • Data Structures and Algorithms
Data Structures and AlgorithmsDiscrete Mathematics
AI summaryⓘ
The authors show how to turn Karger's random method for finding the smallest weighted 'cut' in a matroid into a reliable step-by-step process when a certain ratio related to the matroid's structure is limited. Their method works efficiently without knowing some key parameters ahead of time. They apply this to a special class of matroids influenced by graphs, offering a fixed-parameter efficient way to find these cuts based on rank perturbations. Additionally, their approach can handle variations like listing all near-minimum solutions and optimizing multiple weight criteria.
matroidcocircuitcogirth-density ratiocontraction algorithmperturbed graphic matroidfixed-parameter tractabilityminimum-weight cocircuit1-cocyclek-cocycle
Authors
Yu Cong, Chao Xu, Yajie Zhao
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.