Subquadratic-Query Algorithms for Finding Another Maximum Matroid Intersection

Our results

• A distinct maximum solution exists exactly when the exchange graph contains a directed cycle; a chordless cycle yields another solution.The approach peels sources without constructing the graph.Source: §1 · pp. 1–2
• The O(nr)-query baseline constructs the exchange graph, whose at most 2r(n−r) arcs can each be tested with one independence query.Earlier implicit algorithms had bounds eO(nr3/4) randomized and eO(nr5/6) deterministic [Bli21].Source: §1 · pp. 1–2
• The Las Vegas algorithm uses eO(n√r) expected independence queries, while the deterministic algorithm uses eO(nr2/3) queries.Here n is the ground-set size and r is the given maximum solution size.Source: §1 · p. 2
• The randomized method samples S vertices to classify indegrees of all S vertices collectively; the deterministic method stores in-neighbors as capacity-limited certificates and enumerates possible arcs incident to the small saturated set.Source: §1 · p. 3
• Enumeration of maximum common independent sets uses at most two another-solution calls between consecutive outputs and after the last output, giving query delay of the same asymptotic order as one Another Matroid Intersection call.The resulting expected query delay is eO(n√r), or deterministic query delay is eO(nr2/3).Source: §1 · p. 3

• Another Matroid Intersection asks whether a given maximum common independent set S has a distinct maximum common independent set, and outputs one if it exists.Source: §2 · p. 4
• In the independence-oracle model, each query reports whether a specified subset is independent in either matroid, and the algorithm is measured by its query count.Source: §2 · p. 4
• For a vertex y in S and nonempty X in S, one independence query tests whether y has an exchange-graph neighbor in X.The two matroids test the two arc directions by checking (S \ X) + y.Source: §2 · p. 4
• For equal-size X and Y, a common-independent replacement implies a perfect matching in the corresponding exchange graph; a unique perfect matching also implies independence.This exchange property is stated separately for each matroid.Source: §2 · p. 4

3 Reduction to source peeling

• A distinct maximum common independent set exists if and only if the exchange graph contains a directed cycle, and a chordless directed cycle yields another maximum solution by symmetric difference.The cycle criterion reduces the task to finding a chordless cycle or certifying acyclicity.Source: §3 · p. 5

3.1 The directed bipartite query model

• The graph model uses two Boolean queries on a row and a nonempty column subset, and the exchange-graph instance needs one independence query per graph query.Its row and column sides are S and S, respectively.Source: §3.1 · pp. 5–6

3.2 Source peeling and cycle recovery

• Repeated source deletion removes every vertex exactly when the graph is acyclic; a remaining source-free graph contains a cycle that can be shortened to chordless form.The cycle can be recovered from the remaining active vertices without constructing the whole graph.Source: §3.2 · pp. 7–8
• The two deletion-only structures maintain source peeling on the same shrinking active graph, with separate zero-row and zero-column operations.Source: §3.2 · p. 8

4.1 Maintaining zero rows

• At phase starts, implicit rows are sampled to classify them as heavy or light; light rows become explicit, while heavy rows remain implicit until the next phase.Explicit neighborhoods are maintained after column deletions, so a row is emitted when its stored neighborhood becomes empty.Source: §4 · p. 8, §4.1 · p. 9

4.2 Maintaining zero columns

• Because the oracle cannot directly test whether a column has a neighbor in a row subset, the algorithm classifies implicit columns collectively by sampling rows and calling CollectOut.Light columns are made explicit together, and their neighborhoods are maintained after row deletions.Source: §4.2 · pp. 10–11

4.3 Source peeling and the randomized bound

• The two structures share active sets and a source queue, so deleting emitted sources implements source peeling; a nonempty source-free remainder yields a chordless directed cycle.The randomized routine can be restarted after a query cap or failed source verification, giving a Las Vegas algorithm with constant expected trials.Source: §4.3 · pp. 12–13
• The Las Vegas algorithm finds another maximum common independent set using expected independence queries.Its source-peeling routine finds a chordless directed cycle or correctly reports that the graph is acyclic, with the same expected query bound as the high-probability routine.Source: §4.3 · pp. 12–13

5.1 Deterministic zero rows by minimum-load witnesses

• For zero-row maintenance, each active row stores an in-neighbor witness or searches for a minimum-load witness, emitting the row when no active in-neighbor remains.The minimum-load witness structure emits exactly all active zero-indegree rows under column deletions and row deactivations.Source: §5.1 · pp. 13–14

5.2 Deterministic zero columns by capacity saturation

• Capacity saturation supplies deterministic zero-column maintenance where the existing categorization does not provide a transposed structure under the asymmetric query interface.A row's capacity limits witness incidences; saturated rows are enumerated collectively when a deficient column cannot acquire enough witnesses.Source: §5.2 · p. 15
• After each repair, every regular column has h distinct active witnesses, so fewer than h row deletions cannot make it a source before the next repair.The h-th deletion triggers a repair that makes any still-deficient column explicit and checks its exact neighborhood.Source: §5.2 · p. 18

5.3 Putting the deterministic structures together

• The exact zero-row and zero-column structures share active sets and a source queue, implementing deterministic source peeling on the same graph.If peeling leaves a nonempty source-free graph, the routine recovers a chordless directed cycle.Source: §5.3 · p. 19
• The deterministic source-peeling routine finds a chordless directed cycle or correctly reports that the exchange graph is acyclic using graph queries.Applied to the exchange graph, a returned chordless cycle yields another maximum common independent set.Source: §5.3 · p. 19

6 Enumerating maximum common independent sets

• 2L −1 another-solution calls suffice to enumerate L maximum common independent sets, with at most two calls between outputs and after the last output.The enumeration uses polynomial space and has query delay O(A(n, r)) when another-solution calls use A(n, r) queries.Source: §6 · pp. 20–21
• The recursive procedure partitions each constrained family by fixing one previously unfixed element as included or excluded.A constrained family contains common independent sets of size r satisfying the inclusion set In and avoiding the exclusion set Ex.Source: §6 · pp. 20–21
• Each processed subproblem stores a known solution, and Another asks for a different member or reports that none exists.The constrained call is implemented by contracting In and deleting Ex; derived independence queries use one original query.Source: §6 · p. 20
• The recursive procedure outputs every maximum common independent set exactly once.The proof establishes this by induction on the size of the solution family.Source: §6 · p. 21
• After an output, the algorithm tests the excluding child and then the including child; a stored answer can be output without another query during backtracking.The first output is given, and the call producing the second output uses one another-solution invocation.Source: §6 · pp. 20–21
• All maximum common independent sets can be enumerated with expected query delay eO(n√r) by a Las Vegas algorithm or deterministic query delay eO(nr2/3).These bounds apply using the corresponding another-solution algorithms.Source: §6 · p. 22

Declaration of Generative AI Use

• ChatGPT 5.6 sol helped generate proof details and draft the manuscript; the author contributed the algorithmic idea and verified and revised the proof and manuscript.The author takes full responsibility for the paper.Source: Declaration of Generative AI Use · p. 22

A Concentration calculations

• For Lemmas 4.1 and 4.3, the probability calculations require only the stated standard form of Hoeffding’s inequality, when X1, …, XL are independent random variables taking values in [0, 1].Source: A Concentration calculations · p. 23

A.1 Row classification

• Independent column samples make the HasIn indicators independent Bernoulli variables with a common mean.For a row of degree d, the proof considers the case d < 2h and uses a union bound over its in-neighbors.Source: §A.1 · pp. 23–24
• A row is labeled heavy only if X ≥ 3/4, while it is labeled light only if X < 3/4.The proof invokes Equation (1) to bound these classification events.Source: §A.1 · p. 24

A.2 Collective column classification

• When s < 4h, every active column has degree below 4h, so every implicit column is labeled light and both lemma implications hold deterministically.Source: §A.2 · p. 24
• For a fixed implicit column, detections across experiments are independent Bernoulli variables because the sampled sets are independent.Source: §A.2 · p. 24
• For s ≥ 4h, the proof bounds detection using membership and avoidance probabilities for uniform k-element sets, then applies a lower-tail bound.For d < 2h it uses a union bound over the column's active in-neighborhood; the high-degree case establishes µ ≥ 1 − e^-2.Source: §A.2 · pp. 24–25