6.3 Matroid intersection

Matroid intersection combines two matroids on the same ground set, generalizing many optimization problems. It finds the largest common independent set, bridging different matroid structures and providing a powerful framework for solving complex combinatorial challenges.

The algorithm for matroid intersection uses augmenting path techniques, iteratively improving a common independent set. This approach generalizes methods from bipartite matching, showcasing the deep connections between matroid theory and graph algorithms in combinatorial optimization.

Definition of matroids

• Matroids provide a mathematical framework for generalizing the concept of linear independence in vector spaces
• Matroids play a crucial role in combinatorial optimization by capturing the essence of greedy algorithms and their optimality

Properties of matroids

• Independence axioms define matroid structure
  • Ground set E contains all elements
  • Independent set family I satisfies specific conditions
• Hereditary property ensures subsets of independent sets remain independent
• Augmentation property allows extending smaller independent sets
• Rank function measures the size of largest independent set in a subset
• Closure operator determines the span of a set within the matroid

Examples of matroids

• Vector matroid represents linear independence in vector spaces
• Graphic matroid captures cycle-free subsets of edges in a graph
• Uniform matroid where any k-element subset is independent
• Partition matroid based on partitioned ground set with element limits
• Transversal matroid derived from matchings in bipartite graphs

Matroid representation

• Matrix representation for vector matroids using column vectors
• Graph representation for graphic matroids using edge sets
• Binary representation as a collection of binary vectors
• Algebraic representation using polynomial rings
• Oracle representation for abstract access to independence testing

Matroid intersection problem

• Matroid intersection combines two matroids defined on the same ground set
• This problem generalizes many combinatorial optimization scenarios, bridging different matroid structures

Problem statement

• Find the largest common independent set in two matroids
• Maximize $|X|$ such that $X \in I_1 \cap I_2$
• $I_1$ and $I_2$ represent independent set families of two matroids
• Constraint satisfaction requires meeting independence criteria for both matroids

Applications of matroid intersection

• Bipartite matching maps to intersection of two partition matroids
• Task scheduling with resource constraints uses matroid intersection
• Network design problems leverage graphic and partition matroid intersections
• Optimal spanning tree selection in colored graphs
• Assigning jobs to machines with compatibility requirements

Complexity of matroid intersection

• Polynomial-time solvable for two matroids
• NP-hard for three or more matroid intersections
• Strongly polynomial algorithms exist for oracle-based representations
• Complexity depends on matroid representation and access model
• Trade-offs between time complexity and query complexity in oracle model

Matroid intersection algorithm

• Efficient algorithms for matroid intersection rely on augmenting path techniques
• These algorithms generalize methods used in maximum bipartite matching

Greedy approach

• Fails to solve general matroid intersection problems optimally
• Works for special cases like intersecting a matroid with a uniform matroid
• Provides a 2-approximation for the general case
• Useful for initializing more sophisticated algorithms

Augmenting path method

• Iteratively improves a common independent set
• Searches for alternating paths in the exchange graph
• Exchange graph represents potential element swaps between matroids
• Augmenting paths indicate how to increase the common independent set size

Algorithm steps

• Initialize with a feasible common independent set (possibly empty)
• Construct the exchange graph based on current solution
• Search for an augmenting path in the exchange graph
• If found, apply the augmenting path to increase solution size
• Repeat until no augmenting path exists
• Final solution is a maximum common independent set

Time complexity analysis

• $O(nr)$ time per augmentation, where n is ground set size and r is matroid rank
• Total runtime $O(nr^2)$ for matroids with rank r
• Improvements possible with more sophisticated data structures
• Parallel algorithms can reduce time complexity in certain settings

Weighted matroid intersection

• Extends the matroid intersection problem by assigning weights to elements
• Seeks to maximize the total weight of the common independent set

Problem formulation

• Given: Two matroids $M_1 = (E, I_1)$ and $M_2 = (E, I_2)$, weight function $w: E \rightarrow \mathbb{R}$
• Objective: Maximize $\sum_{e \in X} w(e)$ subject to $X \in I_1 \cap I_2$
• Generalizes maximum weight bipartite matching and other weighted problems

Optimal solution characteristics

• Optimal solution satisfies a local optimality condition
• No single element exchange can improve the solution weight
• Characterized by absence of negative-weight cycles in exchange graph
• Optimality certificate provided by dual variables in linear programming formulation

Algorithms for weighted intersection

• Frank's weight-scaling algorithm achieves strongly polynomial time
• Cunningham's algorithm uses a primal-dual approach
• Algebraic algorithms leverage fast matrix multiplication techniques
• Approximation algorithms provide near-optimal solutions in faster time
• Combinatorial algorithms often outperform LP-based methods in practice

Matroid partition

• Decomposes a matroid's ground set into disjoint independent sets
• Closely related to matroid intersection through duality

Relation to matroid intersection

• Matroid partition dual to matroid intersection problem
• Maximum size partition equals minimum number of spanning sets
• Algorithms for intersection adapt to solve partition problems
• Partition provides insights into matroid structure and properties

Edmonds-Fulkerson theorem

• Characterizes the maximum number of disjoint bases in a matroid
• States that the maximum number equals the minimum rank quotient
• Generalizes Hall's marriage theorem for bipartite graphs
• Provides a min-max relation fundamental to matroid theory

Partition algorithm

• Iteratively construct partitions by adding elements
• Maintain feasibility by swapping elements between partitions
• Use augmenting path techniques similar to matroid intersection
• Terminate when no further improvements possible
• Final partition achieves maximum size guaranteed by Edmonds-Fulkerson theorem

Matroid union

• Combines multiple matroids to form a new matroid structure
• Offers a dual perspective to matroid intersection

Definition and properties

• Union of matroids $M_1, \ldots, M_k$ defined on ground sets $E_1, \ldots, E_k$
• Independent sets in union are unions of independent sets from component matroids
• Rank function of union relates to sum of component ranks
• Closure and circuit properties derive from component matroids

Union vs intersection

• Union focuses on combining structures, intersection on finding common elements
• Union preserves matroid properties, intersection result may not be a matroid
• Algorithms for union often simpler than intersection algorithms
• Union useful for constructing new matroids, intersection for optimization

Applications of matroid union

• Modeling resource allocation with multiple constraint types
• Analyzing connectivity in graphs and hypergraphs
• Solving packing problems in combinatorial optimization
• Constructing matroids with desired properties for algorithm design
• Theoretical tool for proving results in matroid theory

Submodular functions

• Generalize the concept of convexity to discrete settings
• Provide a bridge between continuous and discrete optimization

Connection to matroids

• Matroid rank functions are submodular
• Greedy algorithms optimal for submodular function maximization over matroids
• Submodular minimization generalizes certain matroid optimization problems
• Lovász extension connects submodular functions to convex analysis

Submodular optimization

• Maximization NP-hard but admits constant-factor approximations
• Minimization solvable in polynomial time using various methods
• Continuous relaxations lead to efficient algorithms (Fujishige-Wolfe algorithm)
• Applications in machine learning, computer vision, and information theory
• Matroid constraints often appear in submodular optimization problems

Matroid intersection in graph theory

• Many graph theory problems can be formulated as matroid intersection
• Provides efficient algorithms and structural insights for graph problems

Bipartite matching

• Maximum bipartite matching as intersection of two partition matroids
• One matroid for row selection, another for column selection
• Augmenting path algorithm for matching maps to matroid intersection algorithm
• Weighted bipartite matching solved by weighted matroid intersection

Arborescences

• Directed spanning trees (arborescences) found using matroid intersection
• Intersection of graphic matroid and partition matroid
• Edmonds' algorithm for maximum arborescence uses matroid intersection principles
• Generalizes to optimal branchings and directed forests

Network flows

• Certain network flow problems reformulated as matroid intersection
• Maximum flow in planar graphs solved using graphic matroid intersection
• Matroid intersection provides alternative algorithms for flow problems
• Helps identify combinatorial structure in network optimization

Extensions and generalizations

• Research continues to expand the scope and applicability of matroid intersection

Polymatroid intersection

• Generalizes matroid intersection to continuous setting
• Submodular function constraints replace independence constraints
• Applications in resource allocation and information theory
• Algorithms adapt continuous optimization techniques

Matroid parity problem

• Find maximum set of disjoint pairs in matroid
• Generally NP-hard but polynomial-time for linear matroids
• Lovász's algebraic algorithm solves linear matroid parity
• Applications in graph theory and combinatorial optimization

Matroid base packing

• Partition ground set into maximum number of bases
• Generalizes edge-disjoint spanning tree packing
• Algorithms use matroid intersection as a subroutine
• Applications in network reliability and graph decomposition

Computational aspects

• Implementation considerations crucial for practical matroid algorithms

Oracle model

• Abstract access to matroid through independence oracle
• Allows analysis of algorithms independent of matroid representation
• Query complexity measures algorithm efficiency in oracle model
• Trade-offs between time complexity and query complexity

Hardness results

• Three-matroid intersection NP-complete
• Matroid matching NP-complete for general matroids
• Weighted matroid intersection admits FPTAS but no PTAS unless P=NP
• Parameterized complexity results for various matroid problems

Approximation algorithms

• (1-ε)-approximation for weighted matroid intersection
• Greedy algorithms provide constant-factor approximations for many problems
• Local search techniques yield improved approximation ratios
• Online and streaming algorithms for matroid optimization under constraints