Greedy choice and matroids (greedoids)

Question

As I was going through the material about the greedy approach, I came to know that a knowledge on matroids (greedoids) will help me approaching the problem properly. After reading about matroids I have roughly understood what matroids are. But how do you use the concept of a matroid for solving a given optimisation problem?

Take, for example, the activity selection problem. What are the steps to use matroid theory for solving the problem?

Answer 1

The connection is that if a you can represent the structure underlying your optimisation problem as matroid, you can use the canonical greedy algorithm to optimise the sum of any positive weight function. If your optimisation goal fits this paradigm, you can solve your problem with the greedy approach.

Example

Consider the minimum spanning tree problem with positive edge weights¹. We will show that there is a matroid corresponding to that problem, implying that it can be solved greedily, that is by the canonical greedy algorithm on said matroid.

Let $G = (V,E,c)$ be an undirected graph with $c : E \to \mathbb{R}_+$ the edge-cost function. Then, $(E,I)$ with

$\qquad \displaystyle I = \{F \subseteq E \mid (V|_F, F) \text{ is a forest}\}$²

is a matroid. Thus, we can find the element of $I$ maximising the sum of edge weights $c'(e) = (\max_{e \in E}c(e)) - c(e)$. This happens to be a minimum spanning tree. Note that the canonical greedy algorithm is called Kruskal's algorithm in this context for historical reasons.

Proofs

1. To show: $(E,I)$ is a matroid. We have to verify three properties:

   • $\emptyset \in I$ -- the empty graph is a forest.
   • If $F \in I$, every subset of $F$ is in $I$ -- given an arbitrary forest, removing edges can not introduce cycles. Therefore, every subgraph of a forest is a forest.
   • For every $F_1,F_2 \in I$, $|F_1| > |F_2|$ implies that there is $e \in F_1 \setminus F_2$ so that $F_2 \cup \{e\} \in I$ -- consider an arbitrary forest $F_1$ and a smaller one $F_2$. Assume there is no such $e$. That means that all edges in $F_1$ lie in cuts induced by edges in $F_2$³. As there are only $|F_2|$ such cuts, at least one pair of edges in $F_1$ shares a cut; this contradicts that $F_1$ is a forest.

2. To show: any element $F^*$ with maximum weight in $I$ is a minimum spanning tree of $G$. First of all, it is clear $F^*$ has maximum weight according to $c'$, so by definition of $c'$, it also has minimum weight according to $c$. Now all we have to show is that it is a spanning tree: if it was not, it would not be maximal in the sense that we could still add edges (with positive weight), contradicting maximum weight.

---

1. We can deal with negative edge weights by adding the minimum weight plus one to all weights.
2. A forest is a disjoint union of trees.
3. A graph contains a cycle if and only if there is a cut with more than one edge.