Matroid

Introduction

Matroid is an abstract algebraic structure proposed by Hassler Whitney in 1935 to unify and generalize the concept of independence, such as linear independence in linear algebra and acyclicity in graph theory.

Matroids provide a powerful theoretical tool for optimization problems involving independence. They are widely used in combinatorics, graph theory, and algorithm design, especially by providing mathematical foundations for optimization methods such as greedy algorithms.

Definition

Matroid

A matroid can be represented as $M = (E, \mathcal{I})$, where:

• $E$ is a finite set called the ground set.

• $\mathcal{I}$ is a family of subsets of $E$ called the family of independent sets; its members are called independent sets. It has the following three properties:

  • Non-emptiness: The empty set is independent, that is, $\emptyset \in \mathcal{I}$.

  • Hereditary property: Every subset of an independent set is independent. If $I \in \mathcal{I}$, then for every $I' \subseteq I$, we have $I' \in \mathcal{I}$.

  • Augmentation property: If $I, J \in \mathcal{I}$ and $|I| < |J|$, then there exists $j \in J \setminus I$ such that $I \cup \{j\} \in \mathcal{I}$.

A structure of the form $(E, \mathcal{I})$ that satisfies these three properties is called a matroid.

Basis

A basis is a maximal independent set in a matroid, that is, an independent set to which no element can be added while preserving independence. The collection of all bases is called the family of bases, denoted by $\mathcal{B}$.

Properties:

1. Equal cardinality: All bases have the same size, called the rank of the matroid.

2. Augmentation property: Any independent set can be extended to a basis by adding elements from a basis.

Circuit

A circuit is a minimal dependent set in a matroid: all its proper subsets are independent, while the set itself is not independent. No two circuits contain one another.

Rank

The rank function $r: 2^E \rightarrow \mathbb{Z}_{\geq 0}$ maps subsets of the ground set $E$ to non-negative integers. For any $S \subseteq E$, $r(S)$ is defined as the size of the largest independent set in $S$, namely

$$r(S) = \max \{ |I| \mid I \subseteq S \wedge I \in \mathcal{I} \}.$$

Properties:

1. Non-negativity: For any $S \subseteq E$, $0 \leq r(S) \leq |S|$.

2. Monotonicity: If $A \subseteq B \subseteq E$, then $r(A) \leq r(B)$.

3. Submodularity: For any $A, B \subseteq E$, $r(A \cup B) + r(A \cap B) \leq r(A) + r(B)$.

Typical Examples

1. Uniform Matroid

Definition: Given a ground set $E$ and a non-negative integer $k$, the family of independent sets of the uniform matroid $U_{k,E}$ consists of all subsets of size at most $k$, written as

$$\mathcal{I} = \{ I \subseteq E \mid |I| \leq k \}．$$

• Bases: All subsets of size $k$.

• Circuits: All subsets of size $k + 1$.

• Rank: $r(E) = \min(k, |E|)$, meaning that an independent set can contain at most $k$ elements.

2. Graphical Matroid

Definition: Given an undirected graph $G = (V, E)$, the ground set of the graphical matroid $M(G)$ is the edge set $E$, and its family of independent sets consists of all edge sets containing no cycle, namely all forests.

• Bases: Spanning trees of the graph (when the graph is connected). A spanning tree is a maximal independent set: no edge can be added without creating a cycle.

• Circuits: Simple cycles in the graph. Removing any edge from a cycle leaves an independent set.

• Rank: $r(E) = |V| - c$, where $c$ is the number of connected components of the graph. For a connected undirected graph, its rank equals the number of vertices minus one, namely $|V| - 1$.

3. Linear Matroid

Definition: A linear matroid is based on a vector space. Given a vector space $V$, the ground set $E$ is a finite collection of vectors in $V$, and its family of independent sets consists of all subsets of $E$ that are linearly independent.

• Bases: Maximal linearly independent sets, whose size equals the dimension of the vector space.

• Circuits: Minimal linearly dependent sets of vectors; every proper subset is independent, while the set itself is linearly dependent.

• Rank: The rank of a linear matroid is $r(E) = \dim(V)$, namely the dimension of the vector space. The size of an independent set cannot exceed the dimension of the vector space.

4. Partition Matroid

Definition: Partition the ground set $E$ into disjoint subsets $E_1, E_2, \dots, E_m$, and specify for each subset $E_i$ a non-negative integer $k_i$. The family of independent sets of the partition matroid consists of subsets that select at most $k_i$ elements from each part, written as

$$\mathcal{I} = \left\{ I \subseteq E \mid \forall i,\, |I \cap E_i| \leq k_i \right\}．$$

• Bases: An independent set satisfying $|I \cap E_i| = k_i$ is a basis of the partition matroid. Each basis selects exactly $k_i$ elements from each subset.

• Circuits: A circuit of a partition matroid is a minimal dependent set, namely a set containing at least one subset with more than $k_i$ elements.

• Rank: The rank of a partition matroid is $r(E) = \sum_{i=1}^m k_i$, meaning that the largest independent set has size equal to the sum of the maximum permitted numbers of elements selected from the subsets.

5. Colored Matroid

Definition: A colored matroid is a special form of partition matroid in which every element is assigned a color. Given a ground set $E$ and a color set $C$, each element $e \in E$ is associated with a color $c \in C$. The independent sets of a colored matroid must satisfy not only the independence condition of an ordinary matroid but also color-specific restrictions, such as selecting at most a certain number of elements of the same color.

• Bases: Maximal independent sets that satisfy the color restrictions and independence conditions.

• Circuits: Minimal dependent sets containing at least one set of elements that violates independence or a color restriction.

• Rank: The rank of a colored matroid is the size of the largest independent set satisfying the color restrictions. It depends both on the structure of the matroid and on the specific color restrictions.

Constructions and Operations

Dual

Given a matroid $M = (E, \mathcal{I})$, its dual matroid $M^* = (E, \mathcal{I}^*)$ is defined by

$$\mathcal{I}^* = \{ I^* \subseteq E \mid \exists B \in \mathcal{I}, |B| = r(E), B \subseteq E \setminus I^* \}．$$

Properties:

• Bases: The bases of the dual matroid $M^*$ are the complements of the bases of $M$ in the ground set $E$. In other words, if $B$ is a basis of $M$, then $E \setminus B$ is a basis of $M^*$.

• Rank function: The rank function of the dual matroid is $r^*(S) = |S| - r(E) + r(E \setminus S)$, where $S$ is a subset of $E$. Thus, the rank of the dual matroid can be computed from the size of the ground set, the rank of the original matroid, and the rank after removing $S$ from the ground set.

• Involution: The dual of the dual matroid is the original matroid, that is, $(M^*)^* = M$.

Example:

For an undirected graph $G = (V, E)$, the graphical matroid $M(G)$ has dual $M(G)^*$, which is the matroid formed by the cuts of the graph. The bases of $M(G)$ are the spanning trees of the graph, while the bases of its dual $M(G)^*$ are the complements of those spanning trees. The circuits of the dual $M(G)^*$ are the minimal cuts of the graph, namely the minimal edge sets whose removal separates the graph into two disconnected parts.

For example, consider a simple triangle graph $G$ with edge set $E = \{e_1, e_2, e_3\}$. The bases of the graphical matroid $M(G)$ are sets of two edges, such as $\{e_1, e_2\}$, while the bases of the dual matroid $M(G)^*$ are singleton edge sets, such as $\{e_3\}$. The circuits of $M(G)^*$ are sets of two edges (that is, minimal cuts, such as $\{e_2,e_3\}$), because removing either edge separates the graph into two connected components.

Deletion and Contraction

Deletion:

For $A \subseteq E$, the matroid $M$ after deleting $A$ gives a new matroid $M \setminus A$, whose family of independent sets $\mathcal{I}'$ is defined as

$$\mathcal{I}' = \{ I \subseteq E \setminus A \mid I \in \mathcal{I} \}．$$

The deletion operation can be understood as removing some elements from the matroid and retaining the independent sets formed by the remaining elements. It preserves the original independence relation while removing those elements.

Contraction:

For $A \subseteq E$, the matroid $M$ after contracting $A$ gives a matroid $M / A$, whose family of independent sets $\mathcal{I}''$ is defined as

$$\mathcal{I}'' = \left\{ I \subseteq E \setminus A \,\bigg|\, \exists B \subseteq A,\, B \in \mathcal{I},\, r(B) = r(A),\, I \cup B \in \mathcal{I} \right\}$$

The contraction operation can be understood as contracting the elements of $A$ and considering independent sets formed by the remaining elements together with a basis of $A$. The result of contraction depends on the basis of $A$; the contracted independent sets are effectively obtained by reducing higher-rank subsets of the original matroid.

Example — Graphical Matroid:

• Deletion: In a graphical matroid, deletion means removing some edges from the graph. After deleting an edge from a graph $G$, consider the independent sets formed by the remaining edges, namely edge sets containing no cycle. For example, deleting one edge from a triangle leaves two edges that still form a forest.

• Contraction: Contraction turns an edge into a vertex. In a graphical matroid, contracting an edge is equivalent to merging its two endpoints into one vertex and deleting the edge; after the merge, the other edges in the graph can still form independent sets. For example, contracting any edge in a triangle merges two vertices into one, and the remaining two edges form a new matroid.

Matroids and Greedy Algorithms

Problem Statement:

One application of matroids is solving optimization problems with greedy algorithms. Specifically, given a matroid $M = (S, \mathcal{I})$, where $S$ is the ground set and $\mathcal{I}$ is the family of independent sets, assign each element $x \in S$ a positive integer weight $w(x)$ and seek an independent set of maximum weight, formalized as

$$\max_{A \in \mathcal{I}} w(A) = \max_{A \in \mathcal{I}} \sum_{x \in A} w(x)$$

Clearly, a maximum-weight independent set must be maximal. If an independent set $A$ is not maximal, there is an element that can be added to $A$, namely $x$; since $w(x) > 0$, adding it increases the weight, so $A$ cannot be a maximum-weight independent set.

Steps

The greedy algorithm for finding a maximum-weight independent set proceeds as follows:

1. Sort elements: Sort the ground set $S$ by weight in descending order, calling the resulting sequence $e_1, e_2, \dots, e_n$.
2. Initialize: Set the independent set $A = \emptyset$.
3. Build the independent set: Consider the sorted elements $e_i$ in order. If $A \cup \{ e_i \} \in \mathcal{I}$, update $A = A \cup \{ e_i \}$.
4. Output: The final set $A$ is a maximum-weight independent set.

Complexity Analysis:

Let $n = |S|$ be the size of the ground set, and let $f(n)$ denote the complexity of checking whether a set is independent. The time complexity of the greedy algorithm is

$$O(n \log n + n f(n))$$

Here, $O(n \log n)$ is the complexity of sorting, and $O(n f(n))$ is the complexity of checking independence one element at a time.

Note

• In a graphical matroid, a disjoint-set union can efficiently detect whether a cycle is formed, making $f(n)$ close to constant time.
• In a linear matroid, checking independence usually involves matrix operations, whose complexity depends on the specific implementation.

Correctness Proof:

Let $M = (S, \mathcal{I})$ be a matroid, and let $A \in \mathcal{I}$ be an independent set, with $A$ a subset of some maximum-weight independent set $T$. Define $P = \{ x \in S \setminus A \mid A \cup \{x\} \in \mathcal{I} \}$, the set of all elements that can be added to $A$ while keeping $A$ independent.

Let $y$ be the maximum-weight element in $P$. Then $A' = A \cup \{ y \}$ is also a subset of some maximum-weight independent set, as follows:

Suppose that $A' = A \cup \{ y \}$ is not a subset of any maximum-weight independent set. Then there is a maximum-weight independent set $T$ with $|A'| < |T|$.

Since $|A'|< |T|$, by the augmentation property of the matroid, there exists $x \in T \setminus A'$ such that $A' \cup \{ x \} \in \mathcal{I}$.

Using the augmentation property, repeatedly add $x$ to $A'$, eventually constructing a new independent set $A''$ with $|A''| = |T|$.

Let $K = A'' \cap T$. Then $x = T \setminus K$ and $y = A'' \setminus K$. Since $y$ is the maximum-weight element in $P$, we have $w(x) \leq w(y)$.

Therefore, $w(A'') = w(K) + w(y) \geq w(K) + w(x) = w(T)$, and:

• If $w(A'') > w(T)$, then $T$ is not a maximum-weight independent set, contradicting the assumption.
• If $w(A'') = w(T)$, then $A''$ is a maximum-weight independent set and $A'$ is its subset, contradicting the assumption that $A'$ is not a subset of any maximum-weight independent set.

Thus the assumption is false: $A' = A \cup \{ y \}$ must be a subset of some maximum-weight independent set. Therefore, by repeatedly applying the greedy strategy, we eventually find a maximum-weight independent set.

Example

Minimum Spanning Tree:

Given a connected undirected graph $G = (V, E)$ in which every edge $e \in E$ has weight $w(e)$, the goal is to find a spanning tree containing all vertices with minimum total weight.

Constructing the Matroid:

To formulate the minimum spanning tree problem as a matroid problem, construct the graphical matroid $M(G)$:

• Ground set: $S = E$, namely all edges of the graph.
• Family of independent sets: $\mathcal{I}$ consists of all edge sets containing no cycle (that is, all forests).

Greedy Algorithm:

In the graphical matroid framework, Kruskal's algorithm is a typical matroid-theoretic greedy algorithm for constructing a minimum spanning tree. Although Prim's algorithm is also an effective greedy algorithm that finds a minimum spanning tree, it does not rely strictly on matroid greediness. Therefore, in discussions of matroid theory, Kruskal's algorithm is the primary example of a matroid greedy algorithm.

• Kruskal's algorithm:

  1. Sort edges: Sort all edges in ascending order of weight.
  2. Select incrementally: Select edges in increasing order of weight; if adding an edge does not create a cycle, add it to the spanning tree.
  3. Termination condition: Repeat the process until the spanning tree contains $|V| - 1$ edges.

• Prim's algorithm:

  • Principle: Starting from a vertex, Prim's algorithm gradually expands the spanning tree, each time selecting the minimum-weight edge connecting a vertex inside the tree to one outside it.
  • Although Prim's algorithm is also greedy, its selection strategy differs from that of other greedy algorithms based on the augmentation property of matroids. Therefore, in the strict sense of matroid theory, Prim's algorithm is not considered a typical matroid greedy algorithm.

Matroid Intersection

For two matroids defined on the same ground set $S$, namely $M_1 = (S, \mathcal{I}_1)$ and $M_2 = (S, \mathcal{I}_2)$, if $\mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2$ satisfies the three properties of a matroid family of independent sets, then $M = (S, \mathcal{I})$ is called the intersection of $M_1$ and $M_2$.

Note: The intersection of two arbitrary matroids is not necessarily a matroid. It forms a matroid only when the intersection of their independent-set families satisfies the three properties in the definition of a matroid family of independent sets.

Problem Statement

1. Maximum independent set: Find an independent set of maximum cardinality in $\mathcal{I}_1 \cap \mathcal{I}_2$.
2. Maximum-weight independent set: Given a weight function $w: S \to \mathbb{R}$, find an independent set of maximum total weight in $\mathcal{I}_1 \cap \mathcal{I}_2$.

Algorithm

Unweighted version:

1. Initialization: Choose an initial independent set $I \in \mathcal{I}_1 \cap \mathcal{I}_2$, usually $I = \emptyset$.
2. Iteration:
   • Build the exchange graph: According to the current independent set $I$, build the exchange graph $D_{M_1, M_2}(I)$.
   • Path selection: In the exchange graph, from the source $s$ to the sink $t$, find an augmenting path $P$.
   • Augmentation: Traverse every node along $P$ from $s$ to $t$:
     • If a node belongs to the left part (that is, an element of $I$), remove that element from $I$.
     • If a node belongs to the right part (that is, an element of $S \setminus I$), add that element to $I$.
   • Repeat: After updating $I$, repeat the steps until no new augmenting path can be found.
3. Result: The final independent set $I$ is a maximum independent set in the matroid intersection $M = M_1 \cap M_2$.

Weighted version:

To find an independent set with maximum total weight, optimize the choice of augmenting path.

1. Weight assignment: For each element $e \in S$, define its weight $w'(e)$ in the exchange graph:
   • Left-part vertex (an element of $I$): $w'(e) = -w(e)$.
   • Right-part vertex (an element of $S \setminus I$): $w'(e) = w(e)$.
2. Path selection: In the exchange graph $D_{M_1, M_2}(I)$, from the source $s$ to the sink $t$, find an augmenting path $P$ such that augmenting along the path maximizes the increase in the total weight of $I$.
   • Augmentation condition: The total weight of elements added along $P$ is greater than the total weight of elements removed, namely $\sum_{y \in \text{加入的元素}} w(y) > \sum_{x \in \text{移除的元素}} w(x)$
3. Augmentation: Traverse every node along $P$ from $s$ to $t$:
   • If a node belongs to the left part (that is, an element of $I$), remove that element from $I$.
   • If a node belongs to the right part (that is, an element of $S \setminus I$), add that element to $I$.
4. Iteration: Repeat steps 1 through 3, repeatedly building the exchange graph and finding augmenting paths to improve the total weight of $I$.
5. Termination condition: Terminate when no path satisfying the augmentation condition can be found in the exchange graph.
6. Result: The final independent set $I$ is a maximum-weight independent set in the matroid intersection $M = M_1 \cap M_2$.

Complexity:

• Number of augmentations: If the maximum ranks of the two matroids are $r_1$ and $r_2$, respectively, the maximum number of augmentations is $\min(r_1, r_2)$.

• Complexity of each augmentation:

  • Building the exchange graph takes $O(n^2)$ time, where $n = |S|$.
  • The complexity of finding an augmenting path depends on the path-search strategy and is usually $O(n^2)$, for example when using breadth-first search.

• Total time complexity: The overall time complexity is $O(r \cdot n^2)$, where $r = \min(r_1, r_2)$.

Example Problems

Minimum Spanning Tree:

Given an undirected graph $G = (V, E)$ in which every edge $e \in E$ has weight $w(e)$. Find a spanning tree containing all vertices with minimum total weight.

• For details, see Minimum Spanning Tree.
• Problem template: Luogu P3366 (Template) Minimum Spanning Tree.

Solution Idea

Use Kruskal's algorithm: sort all edges in ascending order of weight, then select edges one by one, adding an edge to the spanning tree if it does not create a cycle. The resulting spanning tree is a minimum spanning tree.

Colorful Graph:

Given an undirected graph with multiple colors $G = (V, E)$, where each edge has a color attribute. Find a largest edge set such that:

1. The selected edges contain no cycle.
2. The number of edges of each color is at most $k$ ($k$ is a given positive integer).

Solution Idea

1. Matroid modeling:

   • Graphical matroid ($M_1$): Defined as all edge sets containing no cycle; the independent-set family $\mathcal{I}_1$ contains all edge sets that do not form a cycle.
   • Color matroid ($M_2$): Defined as edge sets containing at most $k$ edges of each color; the independent-set family $\mathcal{I}_2$ contains all edge sets satisfying the per-color edge bound $\leq k$.

2. Solve the matroid intersection: Solve $M = M_1 \cap M_2$ to find the largest edge set that contains no cycle and uses at most $k$ edges of each color.

Constrained Resource Allocation Problem:

A resource allocation problem has a set of resources $R = \{r_1, r_2, \dots, r_n\}$ and a set of projects $P = \{p_1, p_2, \dots, p_m\}$. Each project $p_i$ requires a certain amount of resources, and the total allocation of each resource cannot exceed its supply.

Goal: Find a resource allocation plan that satisfies all project requirements without exceeding the resource supplies.

Solution Idea

1. Matroid modeling:

   • Demand matroid ($M_1$): Defined as allocation plans satisfying the resource demands of each project; the independent-set family $\mathcal{I}_1$ contains all resource-allocation sets satisfying the project requirements.
   • Supply matroid ($M_2$): Defined as allocation plans not exceeding the supply of each resource; the independent-set family $\mathcal{I}_2$ contains all resource-allocation sets satisfying the resource-supply constraints.

2. Solve the matroid intersection: Solve $M = M_1 \cap M_2$ to find a resource allocation plan that satisfies all project requirements without exceeding resource supplies.

References and Notes

1. Wikipedia - Matroid
2. Baidu Baike - Matroid
3. Luogu - Matroids and Optimization Problems
4. Luogu - From Matroid Fundamentals to the Shannon Switching Game