kuniga.me > NP-Incompleteness > Lawler and an Introduction to Matroids

11 Nov 2013

Eugene Lawler was an American computer scientist, professor of UC Berkeley and was one of the founders of the field of Combinatorial Optimization.

Lawler made important contributions on branch and bound algorithms, dynamic programming, and was also the first one to observe that matroid intersection could be done in polynomial time.

He also proved that two of Karp’s 21 NP-Complete problems, The Directed Hamiltonian Cycle and 3-Dimensional Matching were NP-Complete.

This is the first post in our series of Matroids in Combinatorial Optimization context. They will be mainly based on the *Matroids and the Greedy Algorithm* chapter from *Combinatorial Optimization - Networks and Matroids*, by Eugene Lawler.

Hassler Whitney developed Matroids in 1935 in the context of algebraic theory and it was further applied by Jack Edmonds in the context of combinatorial optimization.

Matroids are a structure that allows us to solve problems by always taking local optimal steps and by doing that there’s the guarantee we’ll reach the global optimum. These types of algorithms are known as greedy algorithms.

First we’ll define Matroids and then give some examples of problems to modeled as matroids. Next, we’ll introduce weighted matroids and describe a generic algorithm to solve them and how such algorithm applied to matroids in graphs is actually the famous Kruskal algorithm.

Let \(E\) be a set of elements and \(\cal I\) a family of subsets of \(E\) (family here has the meaning of a set of elements that share some properties and it’s also clearer than using ‘set of subsets’). Let \(M = (E, \cal I)\) and consider the following properties:

1) \(\emptyset \in \cal I\) and if a subset \(I \in \cal I\), then all subsets of \(I\) belong to \(\cal I\) as well.

2) If \(I_p \in {\cal I}\) with \(\mid I_p \mid = p\) and \(I_{p+1} \in {\cal I}\) with \(\mid I_{p+1}\mid = p+1\), then there is an element \(e \in I_{p+1} \setminus I_{p}\) such that \(I + e \in {\cal I}\). (*Henceforth, by abuse of notation, when we say \(I + e\) we mean \(I \cup \{e\}\)*).

If \(M\) satisfies both (1) and (2), we say that \(M\) is a matroid.

**Terminology.** An *independent set* is any set \(I\) belonging to the family \(\cal I\). If there’s no other set containing \(I\) in \(\cal I\) we say it’s a *maximal independent set*. Note that by property (2), all maximal independent sets have the same size.

The *rank* of a set \(E\), denoted by \(r(E)\) is the largest independent subset of \(E\). A minimal dependent set is called *circuit*.

We can model some structures as matroids and take advantage of matroids properties to find solutions to problems involving these structures. In this section we’ll present a few examples of such modelings.

The modelling process consists in defining the set \(E\), the family \(\cal I\) (usually by defining the property that the subsets of \(E\) must have to be in there) and then proving that \(\cal I\) satisfies (1) and (2).

**Matric Matroid.**

A *matric matroid* is a matroid in the context of matrices. Given a matrix \(A\) with the set of columns as \(E\), if \(\cal I\) is the family of sets containing only linear independent columns, then \(M = (E, {\cal I})\) is a matric matroid.

*Proof.* It’s easy to see that any subset of a linear independent (LI) set of columns is also LI, so (1) is straightforward. For (2), we need to prove that given subsets \(I_{p+1}\) and \(I_{p}\) of \(p+1\) and \(p\) LI columns, respectively, then there must be a column \(c\) from \(I_{p+1} \setminus I_{p}\) such that \(I_{p} + c\) is still LI. Well, if it’s not the case, it means that each column in \(I_{p+1}\) can be written as linear combination of the \(p\) LI columns from \(I_{p}\), which contradicts the fact that \(I_{p+1}\) is LI.

**Graphic Matroid.**

A *graphic matroid* is a matroid in the context of graphs. Given a graph \(G = (V, E)\), if \(\cal I\) is the family of arcs that do not form a cycle, then \(M = (E, {\cal I})\) is a graphic matroid.

*Proof.* It’s possible to show that subsets of edges that are cycle free, correspond to LI columns in the incidence matrix of \(G\), so in this case we can also view \(M\) as a matric matroid of the incidence matrix of \(G\).

**Matching Matroid.**

A *matching matroid* is a matroid in the context of matchings in graphs.

Let \(G = (V, E)\) be an undirected graph and let \(\cal I\) be the family of subsets of nodes \(I \subseteq V\) such that there’s a matching in \(G\) that covers all nodes in \(I\) (we say that an node in \(I\) is covered if there’s an edge in the matching incident to it, even if the other end of the edge is not in \(I\)). Then \(M = (V, {\cal I})\) is a matching matroid.

*Sketch of the Proof.* It’s easy to verify that \(\cal I\) satisfies (1). The proof of why it satisfies (2) consists in getting the symmetric difference between matchings covering \(p+1\) and \(p\) vertices respectively and showing that in that difference there will be at least one alternating path such that if we change the alternation will increase the number of matched vertices.

Let \(M = (E, {\cal I})\) be a matroid and \(w\) a weight function for elements in \(E\). The problem we want to solve is to find the independent set \(I \in {\cal I}\) that has maximum weight, where the weight of a set is the sum of the weight of its elements.

Let’s assume the elements on each independent set are listed in the non-increasing order of weight, so given sets \(I_1\) and \(I_2\), we list them as

\(I_1 = \{a_1, a_2, \cdots, a_m\}\) and \(I_2 = \{b_1, b_2, \cdots, b_n\}\)

such that \(w(a_1) \ge w(a_2) \ge \cdots w(a_m)\) and \(w(b_1) \ge w(b_2) \ge \cdots w(b_n)\)

We say \(I_1\) is *lexicographically greater* than \(I_2\) if for the first position their components differ, say at index \(k\), \(a_k > b_k\) or in case \(I_2\) listing is a prefix of \(I_1\) listing (that is, the same way we sort strings).

A set that is not lexicographically less than any other set is said to be *lexicographically maximum*. We can show such set is also a maximum independent set, because otherwise, by property (2), we can always add more elements to it, making it lexicographically greater.

The following Theorem from Rado and Edmonds states an important property of weighted matroids:

Theorem 1.Let \(M = (E, {\cal I})\) be a matroid. Then3) For any negative weight function on \(E\), a lexicographically maximum set in \(\cal I\) is also the set with the maximum weight.

Conversely, given \(E\) and \(\cal I\), if (1) and (3) are satisfied, \(M = (E, {\cal I})\) is a matroid.

We say that a set \(B \in {\cal I}\) is *Gale optimal* if all its components are not less than the corresponding components of any other set \(I \in {\cal I}\) when these components are listed in non-increasing order. More formally, there exists a one-to-one mapping \(h:I \rightarrow B\) such that \(w(e) \le w(h(e))\) for all \(e \in I\).

Note that a Gale optimal set is clearly a lexicographically maximum and thus has optimal weight.

Given that, Gale’s theorem provides another a stronger result than Theorem 1 regarding weighted matroids:

Theorem 2.Let \(M = (E, {\cal I})\) be a matroid. Then4) For any weight function of elements on \(E\), there exists a Gale optimal set \(B \in {\cal I}\).

Conversely, given \(E\) and \(\cal I\), if (1) and (4) are satisfied, \(M = (E, {\cal I})\) is a matroid.

**Weighted Matroid Greedy Algorithm.** Property (4) allows to use a simple greedy algorithm to find the set of the largest weight in \(\cal I\).

In the first step, we look for the single-element set \(I = \{e_0\}\) in \(\cal I\) with the largest weight. By property (2) and (4), we can show that the Gale optimal set contains \(e_0\). Next, we look for the largest element \(e_1\) such that \(\{e_0, e_1\} \in {\cal I}\). Again, we can show that such elements are contained in the Gale optimal set. We repeat this until we get a maximum independent set, which is also the Gale optimal set.

More generically, we have the following algorithm:

Let \(S\) be our current solution, which starts as the empty set. At each step, we look for the element \(e\) with maximum weight not in \(S\) such that \(S + e\) belongs to \(\cal I\).

**The Maximum Spanning Tree problem and the Kruskal Algorithm.**

In the maximum spanning tree problem we are given a connected, undirected graph \(G = (V,E)\) with non-negative weights \(w\) on \(V\) and we want to find a spanning tree (subset of \(E\) that forms a tree) with the lowest cost.

Recall that a tree is a connected graph without cycles. The graphic matroid represents cycle-free subsets of arcs (or a forest) and thus the maximum independent set of a connected graph is a tree. If we assign non-negative weights to arcs, we can find the optimal Gale independent set which corresponds to the maximum spanning tree.

The Kruskal algorithm is then basically an application of the weighted matroid greedy algorithm for graphic matroids: It first sorts the edges by non-increasing order of weight and then adds an edge to the current solution if it doesn’t form a cycle.

In this post we learned the basics of matroids and weighted matroids. In future posts we’ll study Matroid Intersection, Matroid Partition and other types of matroids like Oriented Matroids.