14.3 Matroids Overview

Many greedy algorithms appear unrelated on the surface. Selecting activities, building minimum spanning trees, choosing independent edges, and constructing certain optimal subsets seem like completely different problems. Yet a common mathematical structure lies beneath them. That structure is called a matroid.

Matroids provide one of the deepest explanations for why greedy algorithms work. They identify an entire class of optimization problems where a simple greedy strategy is guaranteed to produce an optimal solution.

Most algorithm engineers never need to construct matroid proofs in daily work. Nevertheless, understanding the basic ideas gives powerful intuition about when greedy methods succeed and when they fail.

Problem

Identify the structural conditions that guarantee the correctness of greedy algorithms.

Motivation

Consider two problems.

Activity Selection

Choose the maximum number of non-overlapping activities.

Greedy solution:

Select the activity with the earliest finishing time.

Minimum Spanning Tree

Choose edges connecting all vertices with minimum total weight.

Greedy solution:

Select the smallest valid edge.

The algorithms look completely different.

One operates on intervals.

The other operates on graphs.

Yet both succeed because they satisfy the same underlying structural properties.

Matroid theory formalizes these properties.

Independence Systems

A matroid begins with a finite set of elements.

Let

$$ E = {e_1,e_2,\ldots,e_n} $$

be the ground set.

Some subsets of (E) are considered independent.

The collection of all independent subsets is denoted by:

$$ \mathcal{I} $$

Example:

Suppose

$$ E={a,b,c} $$

and

$$ \mathcal{I} = { \emptyset, {a}, {b}, {c}, {a,b}, {a,c} } $$

The subset

$$ {b,c} $$

might be forbidden.

The exact interpretation depends on the problem.

In graph problems, independent sets might mean:

• Sets of edges containing no cycles.
• Sets of vertices containing no conflicts.

The definition remains abstract.

Hereditary Property

The first requirement is:

Every subset of an independent set must also be independent.

Formally:

If

$$ A \in \mathcal{I} $$

and

$$ B \subseteq A $$

then

$$ B \in \mathcal{I} $$

Example:

If a set of graph edges contains no cycle, then removing edges cannot create a cycle.

Therefore forests satisfy the hereditary property.

This property appears naturally in many optimization problems.

Exchange Property

The second requirement is the crucial one.

Suppose:

$$ A,B \in \mathcal{I} $$

with

$$ |A| < |B| $$

Then there exists an element

$$ x \in B \setminus A $$

such that

$$ A \cup {x} $$

remains independent.

This is called the exchange property.

Intuitively:

Smaller independent sets can always grow toward larger independent sets.

This property prevents dead ends.

Without it, a greedy algorithm can become trapped in a locally attractive but globally poor solution.

Definition of a Matroid

A matroid consists of:

1. A finite ground set (E).
2. A collection of independent sets (\mathcal{I}).

Such that:

Hereditary Property

Every subset of an independent set is independent.

Exchange Property

Smaller independent sets can always be extended using elements from larger independent sets.

These two simple rules generate surprisingly rich behavior.

Example: Forests in Graphs

Consider a graph.

Ground set:

$$ E = \text{all edges} $$

Independent sets:

$$ \mathcal{I} = { \text{edge sets containing no cycles} } $$

Any subset of a forest is still a forest.

Therefore the hereditary property holds.

If one forest contains more edges than another, an edge can always be added from the larger forest without creating a cycle.

The exchange property also holds.

Thus forests form a matroid.

This explains why greedy edge selection succeeds in minimum spanning tree algorithms.

Weighted Optimization

Suppose every element has a weight.

Element	Weight
a	10
b	8
c	7
d	3

Goal:

Find the maximum-weight independent set.

For arbitrary optimization problems this may be difficult.

For matroids, a simple greedy algorithm works.

Greedy Algorithm for Matroids

Sort elements by descending weight.

Sort by weight.
For each element:
    Add it if independence remains valid.

This is remarkably simple.

Yet it always produces an optimal solution.

Why It Works

The exchange property guarantees that every greedy choice can be incorporated into some optimal solution.

Whenever a heavier element is chosen, any optimal solution using a lighter conflicting element can exchange them.

This mirrors the exchange arguments from previous sections.

Matroid theory packages all such proofs into one general theorem.

Greedy Matroid Theorem

If:

1. The problem forms a matroid.
2. Elements have weights.

Then:

The greedy algorithm that repeatedly selects the heaviest feasible element produces an optimal solution.

This theorem explains many classical algorithms.

Instead of proving each algorithm separately, we can show that the underlying structure is a matroid.

Optimality follows immediately.

Why Knapsack Is Not a Matroid

Consider capacity:

$$ W = 10 $$

Items:

Item	Weight
A	6
B	5
C	5

Independent sets are subsets whose total weight does not exceed 10.

Consider:

$$ A = {A} $$

and

$$ B = {B,C} $$

We have:

$$ |A| < |B| $$

But neither B nor C can be added to A:

$$ 6+5 > 10 $$

The exchange property fails.

Therefore knapsack does not form a matroid.

This explains why greedy methods fail for 0/1 knapsack.

The structural guarantee is absent.

Examples of Matroid Problems

Minimum Spanning Trees

Independent sets:

Forests.

Greedy algorithm:

Kruskal and Prim.

Graphic Independence

Independent sets:

Acyclic edge sets.

Greedy algorithm:

Repeated safe-edge selection.

Scheduling Variants

Certain deadline scheduling problems form matroids.

Greedy ordering becomes optimal.

Linear Algebra

Ground set:

Vectors.

Independent sets:

Linearly independent subsets.

Greedy basis construction becomes possible.

Examples That Are Not Matroids

Many famous optimization problems violate the exchange property.

Examples include:

• 0/1 Knapsack
• Traveling Salesman Problem
• Longest Path Problem
• General Integer Programming
• Most NP-hard optimization problems

In these domains, greedy methods often produce approximations rather than exact solutions.

Practical Algorithm Design

Most engineers do not explicitly ask:

Is this a matroid?

Instead they ask:

• Can I always exchange choices?
• Can smaller solutions grow toward larger ones?
• Does local optimality imply global optimality?

These questions are informal versions of the matroid conditions.

Recognizing them helps distinguish genuinely greedy problems from problems that merely look greedy.

Relationship to Previous Sections

Section 14.1 introduced the greedy choice property.

Section 14.2 introduced exchange arguments.

Matroids unify both ideas.

The exchange property guarantees that exchange arguments exist.

Those exchange arguments establish the greedy choice property.

The result is a complete theoretical foundation for greedy optimization.

Takeaway

Matroids provide a general mathematical framework that explains why many greedy algorithms are optimal. A matroid consists of a collection of independent sets satisfying hereditary and exchange properties. When these conditions hold, repeatedly selecting the best feasible element always yields an optimal solution. Matroid theory therefore transforms greedy correctness from a collection of isolated proofs into a single unifying principle that applies across scheduling, graph theory, linear algebra, and many other domains.