betaFeedback

WorksComputer Science

Matroid Connectedness and Component Decomposition: Breaking the Quadratic Barrier

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(n2)O(n^2) independence queries on an nn-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 nn elements with O(nlog⁡n)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 Ω(nlog⁡n)Ω(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)O(nh) independence queries, where h≥1h \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.

Paper details

vlnc:W_qdsprzer
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT, Claude

View statement
Looking for related papers…