{"id":"arxiv/2608.16298","url":"https://arxiv.org/abs/2608.16298","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Derandomizing Karger's Contraction Algorithm for Matroids","domain":"cs.DS","source":"arxiv","authors":["Yu Cong","Chao Xu","Yajie Zhao"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-17","reactions":{}}