A Shortest Augmenting Path Algorithm for Linear Matroid Parity

1.1 Background

• General matroid parity generalizes graph matching and matroid intersection, while matrix representations make the linear version polynomial-time solvable.The general version requires exponentially many independence-oracle calls.Source: §1.1 · p. 3
• Shortest augmenting paths had resisted use for linear matroid parity for four decades, with bottlenecks involving Cunningham’s bound, search-order-sensitive paths, and the chicken-and-egg complexity of defining blossoms.Cunningham’s original graph-theoretic proof appears inapplicable because it fails to exploit the matrix representation. Skipping a valid concatenation of search paths can trigger numerical cancellations.Source: §1.1 · p. 3

1.2 Techniques and Contributions

• The algorithm synthesizes the Gabow–Stallmann approach with synchronized blossom formation from the Micali–Vazirani framework, incorporating Iwata and Kobayashi’s reformulation.Source: §1.2 · p. 4
• A novel linear-algebraic argument bounds shortest augmenting-path lengths and generalizes Cunningham’s bound for linear matroid intersection.Source: §1.2 · p. 4
• A tight a priori lower bound on search-path lengths characterizes shortest search paths without enumerating every candidate.Source: §1.2 · p. 4
• The algorithm extends Izumi, Kitamura, and Yamaguchi’s incoming-edge structural properties to linear matroid parity, proving these edges yield shortest search and augmenting paths [16].Source: §1.2 · p. 4
• Deterministic time improves from O(nr^3) or O(nr^ω) to O(nr^2 log r), or O(nr^2) with fast matrix multiplication.The paper also reports that these bounds narrow the gap with randomized bounds.Source: §1.2 · p. 4

1.3 Related Work

• The paper surveys deterministic, randomized, and approximation approaches to matroid parity, then outlines preliminaries, the path-length bound, the algorithm and its proof, complexity, and conclusion.Source: §1.3 · p. 5, §1.4 · p. 5

2.1 Notation and Problem Formulation

• A linear matroid uses the columns of a full-row-rank matrix as its ground set, with independent sets given by linearly independent columns.Source: §2.1 · p. 6

2 Augmenting Path Algorithm for Linear Matroid Parity

• The Gabow–Stallmann algorithm augments an independent parity set by finding a path whose base exchange increases the number of lines.It first extends the set with singleton columns so the resulting set forms a base.Source: §2 · p. 5, §2.2 · p. 6

2.2 Linear-Algebraic Framework

• An augmenting path contains exactly two singletons, has the remaining elements as a union of lines, and requires C[P] to be nonsingular.This condition makes the corresponding base exchange valid; the path need not itself be a path in the auxiliary search graph.Source: §2.2 · p. 6
• Pivoting updates the fundamental cocircuit matrix after base exchange, with O(nrℓ) time for a path of length ℓ or O(nrℓ^(ω−2)) using fast matrix multiplication.Source: §2.2 · p. 7

2.3 Search Procedure

• The auxiliary bipartite graph connects a base vertex to a vertex outside J exactly when the corresponding fundamental-cocircuit entry is nonzero.The search labels alternating paths from singletons, grows through half-labeled lines, and forms blossoms from qualifying cycles.Source: §2.3 · p. 7
• Grow and Blossom operations process labeled vertices in assignment order; paths from different singletons are concatenated to return an augmenting path.A rigorous analysis of processing order and linear-algebraic blossom formation ensures the returned path is valid; if none is found, a dual certificate proves optimality.Source: §2.3 · p. 8

3.1 Motivation and Overview

• For any independent parity set J, Lemma 3.1 gives (ν−|J|)/2 disjoint augmenting paths; with efficient shortest-path identification, this supports O(nr^2 log r) total time.The length bound is obtained by a counting argument.Source: §3.1 · p. 8

3.2 Linear-Algebraic Tools

• A parity base exists exactly when the alternating matrix Φ is nonsingular, and the Pfaffian identity relates its nonsingularity to its determinant.For an alternating matrix K, (Pf K)^2 = det K.Source: §3.2 · p. 9

3.3 Initial Strategy

• The support graph GΦ contains the auxiliary graph G, and a nonzero Pfaffian term yields alternating paths that may still fail to be augmenting because of cancellation.The initial construction alone does not rule out cancellation in det C[P].Source: §3.3 · pp. 9–11

3.4 Complete Approach

• Grouping Pfaffian terms by path and cycle partitions and choosing a finest nonzero-sum partition yields nonsingular blocks and augmenting paths; reduction extends the proof to general instances.The general case is reduced to one with a parity base.Source: §3.4 · pp. 11–12
• The shortest augmenting path has length O(ν/(ν−|J|)) for a non-maximum independent parity set J.This follows from the disjoint augmenting paths of Lemma 3.1.Source: §3.1 · p. 8, §3.4 · p. 12

3.5 Application to Local Search

• The local-search algorithm achieves a (1 + ε)-approximation for linear matroid parity with neighborhood size s(ε) = ⌈1/ε⌉.This parameter generalizes the bound for graph matching.Source: §3.5 · p. 13
• The local-search algorithm also applies without a matrix representation when an independence oracle is available.Known exact algorithms for linear matroid parity rely on a matrix representation.Source: §3.5 · p. 13

4.1.1 Key Features of Our Algorithm

• Grow runs on level-k vertices before Blossom processes edges whose endpoint levels sum to 2k + 1, synchronizing operations by search level.The method also replaces the blossom-formation process with a variant suited to analyzing search-path lengths.Source: §4.1.1 · p. 13
• Dummy lines help find paths whose remaining component induces a nonsingular submatrix, while being excluded from levels that measure path length and base-update cost.The algorithm inserts them by extending the fundamental cocircuit matrix and pivoting; an efficient implementation finds a shortest augmenting path in O(nr) time given that matrix.Source: §4.1.1 · p. 14

4.1.2 Correctness Proof

• For each labeled vertex v, level(v) is at least dist(¯v), the minimum length of a coherent nonsingular path to ¯v; this bound is invariant to dummy-line insertion.The proof establishes the lower bound using the structural properties of P(v) \ {v}.Source: §4.1.2 · pp. 14–15
• The algorithm attains level(v) = dist(¯v) by induction, using Grow triggers from Laplace expansion and Blossom triggers from incoming edges to meet each level deadline.The proof establishes validity, minimality, and optimality; the incoming-edge concept extends work on graph matching to this setting [16].Source: §4.1.2 · pp. 14–15

4.2.1 Notation and Definitions

• A vertex's level counts original lines in its search path, while dummy lines have paired bud and tip vertices and each blossom has an assigned dummy line.Search paths may be modified when dummy lines are inserted, and retired vertices are labeled but unavailable for further search.Source: §4.2.1 · pp. 16–17

4.2.2 Search Procedure

• At each search level, the procedure grows lower-level vertices, then processes edges by endpoint levels; it returns a path when the paths joined by Blossom stem from different singletons.If no path is found and no vertices or edges remain to process, it reports that no augmenting path exists.Source: §4.2.1 · p. 16, §4.2.2 · p. 17
• Blossom backtracks along the two search paths, inserts and pivots around a dummy line, updates affected paths, and registers the merged blossom.After pivoting, edge changes away from the new dummy-line vertices are confined to specified cross-boundary edges; adjacency to the new bud or tip reflects prior adjacency to g or c, respectively.Source: §4.2.2 · pp. 18–19
• After each Blossom operation, the stated properties constrain adjacency involving tips and retired vertices and characterize which edges may change during pivoting.The edge-change characterization allows changes involving the new bud or tip, or certain edges crossing the blossom boundary.Source: §4.2.2 · p. 20

4.3 Super Singleton Reduction

• The reduction extends the graph and matrix with a new line and auxiliary vertices, then adds a unique singleton s0 called a super singleton and updates the base.Figure 3 depicts the graph extension, with black vertices belonging to the new base.Source: §4.3 · pp. 20–21, Figure 3 · p. 21
• The reduction preserves search paths and blossoms, and reduces augmenting-path detection to forming a blossom containing any two original singletons.This gives subsequent proofs a unified treatment of blossom formation and augmenting-path detection.Source: §4.3 · p. 21

• Maximal blossoms partition the search tree except s0, and each induced subgraph T[K(x)] is a tree.Each maximal blossom contains exactly one unlabeled vertex.Source: §4.4 · pp. 22–23
• Any search path entering a maximal blossom K(x) does so through its unique unlabeled vertex.Source: §4.4 · p. 23
• Search paths are simple, have odd length, and alternate between E* edges and lines; consecutive vertices form a search-tree or blossom-forming edge.Source: §4.4 · pp. 21, 23
• Contracting each maximal blossom yields a tree, where K(c) in a Blossom(u, v) operation is the lowest common ancestor of K(u) and K(v).Source: §4.4 · p. 23
• Blossom updates preserve MB1–MB3 and path simplicity in both cases, c = d and c ≠ d.Source: §4.4 · p. 24
• Every search path and the path found by the search procedure is coherent: entering a blossom requires including its introduced dummy line’s endpoints.Source: §4.4 · p. 25

4.5.1 Invariance of Nonsingularity

• For coherent P that includes or avoids each dummy line, C*[P], C*[P ∪ T], and C[P \ T] are either all nonsingular or all singular.Thus, proving nonsingularity of the final output path’s C*[P] suffices to establish the required submatrix condition.Source: §4.5.1 · pp. 25–26

4.5.2 The Search Tree

• An upper vertex x is labeled when an incoming edge of its subtree has endpoints with equal K values; any search path entering an unlabeled x’s subtree must pass through x.Such a path enters via (ρ(x), x) and continues within T(¯x).Source: §4.5.2 · p. 26

4.5.3 Search Order

• The search order preserves structural constraints and level bounds, including that upper vertices labeled during AssignUpperLevel(k, kmax) have level at least kmax.These properties support monotonicity of assigned levels with execution order and constrain which vertices or edges can be examined before labeling.Source: §4.5.3 · pp. 27, 29

4.5.4 Path Decomposition

• The path-decomposition argument inductively establishes unique perfect matchings in G*[L(x) \ {x}] and G*[P(x) \ {x}].For an unlabeled vertex y on P(x), or one with y > x, y is an upper vertex at an even position, and P(x) decomposes around y and its mate.Source: §4.5.4 · p. 30
• Each L(x) has odd cardinality and lies in K(x), and recursively decomposing P(x) yields ordered segments with no edges between distinct L(x_i) blocks.The decomposition has x_1 = ρ(y_1) < ··· < x_k = ρ(y_k) < x_{k+1} = x, with each x_i active for i ≤ k.Source: §4.5.4 · pp. 31–32
• For every labeled vertex x, G*[L(x) \ {x}] has a unique perfect matching, supporting the corresponding property for complete search paths.The proof builds the matching inductively: the unique edge bridging each odd-sized segment to the existing set must be included.Source: §4.5.4 · p. 33
• For every search path P(x), the induced subgraph G*[P(x) \ {x}] has a unique perfect matching.The algorithm’s found augmenting path P likewise induces a subgraph G*[P] with a unique perfect matching.Source: §4.5.4 · p. 33
• The path P \ T found by the algorithm is an augmenting path for the initial base B.Its feasibility follows from the path conditions and nonsingularity of C[P \ T], derived from Corollary 4.31 and Lemmas 4.11–4.12.Source: §4.5.4 · p. 33

4.6.1 Formalization

• Because processing order and numerical cancellation complicate defining shortest search paths, the section uses coherent nonsingular paths and proves labeled vertices attain their minimum distances.The distance is the minimum number of original lines in such a path; the algorithm’s invariant is level(x) = dist(¯x) for every labeled x other than s0.Source: §4.6.1 · pp. 34–35
• The algorithm’s augmenting path P satisfies that P \ T is a shortest augmenting path for the initial base B.The proof reduces this claim using the super singleton reduction.Source: §4.6.1 · p. 36

4.6.2 Lower Vertices

• For lower vertices, path decomposition supplies a triggering edge, and induction shows vertices within the current distance threshold are labeled before AssignLowerLevel(k) completes.AssignLowerLevel(k) preserves the level invariants (LV1)–(LV3).Source: §4.6.2 · pp. 36–37

4.6.3 Upper Vertices

• For upper vertices, a coherent nonsingular path decomposes into an edge entering T(v+) and two smaller coherent nonsingular paths whose portions outside T are disjoint.This decomposition supplies an incoming edge for the Blossom operation when v is a lower vertex and supports verification of the dummy-line claim when v is upper.Source: §4.6.3 · p. 38
• A permutation σ is included in the summation exactly when no edge of Mσ bridges two different components of P.The proof establishes that a bridging edge prevents the required refinement, while the absence of such an edge yields it.Source: §4.6.3 · p. 39
• Pivoting and symmetric difference produce coherent nonsingular paths, and Lemma 4.50 extends a path from ¯v to ¯z into one from s0 to ¯z.The construction uses P(ρ(v)) ∪ {v} ∪ Z; its nonsingularity follows by induction on the decomposition of P(ρ(v)).Source: §4.6.3 · pp. 39–41
• If P \ {x, y} is a union of dummy lines and G*[P] has a perfect matching, then y is a bud and K(x) = K(y), provided x is a tip.The proof forms an alternating path between x and y and uses blossom adjacency properties to establish the endpoint types and common blossom.Source: §4.6.3 · p. 41
• Lemma 4.52 guarantees an incoming edge (y, z) of T(¯v) with dist(¯y) < dist(¯v), dist(¯z) ≤ dist(¯v), and dist(¯y) + dist(¯z) ≤ level(ρ(v)) + dist(¯v).The paths constructed from a shortest coherent nonsingular path to ¯v provide the endpoint distance bounds and ensure the edge is incoming.Source: §4.6.3 · pp. 41–42
• AssignUpperLevel(k, kmax) preserves (LV1)–(LV3): inserted dummy-line tips satisfy (LV3), buds satisfy (LV2), and qualifying upper vertices become labeled.Lemma 4.54 establishes the insertion conditions, and Lemma 4.55 proves preservation at termination, including the case where the incoming-edge endpoints are labeled through earlier assignments.Source: §4.6.3 · pp. 42–43

4.7 Optimality

• The alternating matrix Φ* has rank ν + n + |T|, linking the maximum parity-set size ν to the terminal search structure.The proof obtains this rank by transforming Φ* so that Φ appears as a central submatrix, with rank Φ = ν + n.Source: §4.7 · p. 44
• At termination, removing one unlabeled vertex per assigned-level blossom component leaves a partition with no edges between distinct components.The partition consists of singleton vertices in S, the set U of unlabeled vertices with unlabeled mates, and components W; removing u(W) separates them.Source: §4.7 · p. 44
• The partition and alternating-matrix rank bounds give rank Φ* ≤ n + r + |T| − |S|.The proof bounds odd-sized blocks using their singularity, with the number of odd components equal to |S| + |W|.Source: §4.7 · p. 45
• When the algorithm finds no augmenting path, the rank bound yields ν ≤ r − |S| = |J|, proving the current independent parity set J is maximum.The proof compares rank Φ* = ν + n + |T| with rank Φ* ≤ n + r + |T| − |S|.Source: §4.7 · pp. 44–45

4.8 Implementation Details

• A shortest augmenting path, or its non-existence, can be determined in O(nr) time.This is the stated bound for a single search.Source: §4.8 · p. 46
• Restricting the disjoint-set structure to O(r) base elements makes the inverse-Ackermann factor constant, while O(nr) Find operations take linear total time.The construction uses an internal DSU on LB and pointers from LN to LB.Source: §4.8 · p. 46
• Search-path backtracking through contracted blossoms costs O(n), and explicit path recovery is needed only when an augmenting path is detected.The recovery procedure runs in time linear in path length and completes in O(n).Source: §4.8 · p. 47
• Pruning rows and columns for tips and retired vertices keeps C* at r × n throughout the search, avoiding its growth to O(n).The removed vertices are neither involved in the search nor designated as c or g in later pivoting operations.Source: §4.8 · p. 47
• Pivoting operations across the search take O(nr) total time, using O(n) basic-blossom and O(r) nonbasic-blossom operations.The nested AssignUpperLevel loop also examines at most nr vertex pairs.Source: §4.8 · pp. 46–48

5 Overall Complexity

• O(nr^2 log r) deterministically, or O(nr^2) with fast matrix multiplication, solves the unweighted linear matroid parity problem.Source: §5 · p. 48
• Without fast matrix multiplication, summing shortest-path lengths over |J| = 0, 2, . . . , ν − 2 yields O(nrν log ν), or O(nr^2 log r).Each augmentation takes O(nrℓ) time, where ℓ is the shortest augmenting path length.Source: §5 · p. 48
• With fast matrix multiplication, setting j = (ν − |J|)/2 gives total time O(nrν), hence O(nr^2).Source: §5 · pp. 48–49
• In terms of maximum independent parity set size ν, the two bounds refine to O(nrν log ν) and O(nrν), respectively.Source: §5 · p. 49
• The first bound generalizes Cunningham’s time bound for linear matroid intersection; its fast-multiplication counterpart there also removes the log factor.Source: §5 · p. 49

6 Conclusion

• The shortest-path length bound generalizes Cunningham’s linear matroid intersection bound and supports a PTAS with a much smaller local-search neighborhood for linear matroid parity.Source: §6 · p. 49
• The algorithm solves linear matroid parity in O(nr^2 log r) or O(nr^2), improving prior deterministic bounds O(nr^3) and O(nr^ω).These bounds narrow the gap with randomized bounds O(nr^2) and O(nr^(ω−1)).Source: §6 · p. 49
• Extending the framework to linear delta-matroid parity appears plausible, though removing singletons and generalizing the path-length analysis may pose challenges.Source: §6 · p. 49
• Weighted extensions and computational improvements are proposed as future directions, drawing on techniques for linear matroid intersection.Source: §6 · p. 49