Matroid Algorithms Under Size-Sensitive Independence Oracles
The standard oracle model for matroid algorithms assumes that each independence query can be answered in constant time, regardless of the size of the queried set. While this abstraction has underpinned much of the theoretical progress in matroid optimization, it masks the true computational effort required by these algorithms. In particular, for natural and widely studied classes such as graphic matroids, even a single independence query can require work linear in the size of the set, making the constant-time assumption implausible. We address this gap by introducing a size-sensitive cost model where the cost of a query $Q$ scales with $|Q|$. Nearly linear-time oracle implementations exis...
| Authors | Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz et al. |
|---|---|
| Primary category | cs.DS |
| Published | 30 April 2026 |
| Last updated at source | 30 April 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.