arXiv preprint ·
Random Deletion for Circuits in Regular Matroids
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study a simple random deletion algorithm to find short circuits in regular matroids. Given a regular matroid $M$ with $m$ elements, the algorithm randomly deletes each element independently with probability $1-1/m^{Θ(1/g)}$ where $g$ is the size of a minimum circuit, and returns the remaining set $R$ of elements. We establish the following results: 1. With high probability, $R$ contains no circuit and is therefore independent. 2. For every $α$-approximate minimum circuit $C$ where $α\geq 1$, with probability at least $m^{-O(α)}$, the entire circuit $C$ survives in $R$ and moreover, the minimum number of elements that need to be removed to make $R$ independent is $O(α\log(α+2))$. This yields an algorithmic proof that the number of $α$-approximate minimum circuits is $m^{O(α)}$, improving the previous known bound of $m^{O(α^2)}$ by Gurjar and Vishnoi, and resolving a recent conjecture of Khanna, Putterman, and Song. Our results yield two immediate applications. First, we obtain very simple RNC algorithms for computing the shortest circuit, and for enumerating all $α$-approximate circuits, of a regular matroid without computing the Seymour decomposition. Second, we obtain a randomized parallel algorithm to find a basis of a regular matroid under independence-oracle access. It uses polynomially many independence-oracle queries in $O(\log m)$ adaptive rounds and succeeds with high probability. This follows from the framework of Khanna, Putterman, and Song and the improved counting bound, and extends their result from graphic matroids to regular matroids.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Approximation algorithms for identical parallel machine scheduling with assignment costs
A Nearly Optimal Min-Cut Algorithm for Dynamic Streams
A Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions
Bicriteria Approximate Navigable Graphs in General Metrics
Engineering Lightweight Burrows-Wheeler Transform Construction on the GPU via Prefix-Free Parsing
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.