Matroids

CS F364 — Design & Analysis of Algorithms | Summer 2026

Independence axioms, matroid properties, greedy on weighted matroids, exchange property

← Practice

NoteProblem A1

Let S = \{a,b,c,d\} and \mathcal{I} = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}\}. Is (S,\mathcal{I}) a matroid? If not, which axiom fails?

No, this is not a matroid. The augmentation property fails.

  • Take A = \{a,b\} (size 2) and B = \{c\} (size 1).
  • We need x \in B \setminus A = \{c\} such that A \cup \{x\} \in \mathcal{I}. But \{a,b,c\} \notin \mathcal{I}.
NoteProblem A2

Consider S = \{1,2,3,4\} with \mathcal{I} = \{X \subseteq S : |X| \leq 2\} \cup \{\{1,2,3\}\}.

  1. Verify that \mathcal{I} satisfies the hereditary property.
  2. Does it satisfy the augmentation property? Provide a proof or a counterexample.

Yes, (S,\mathcal{I}) is a matroid. It satisfies all three axioms:

  • Hereditary: All subsets of size \le 2 are clearly in \mathcal{I}. For \{1,2,3\}, all subsets are either of size \le 2 or \{1,2,3\} itself, so they are all in \mathcal{I}.
  • \emptyset \in \mathcal{I}: yes.
  • Augmentation: For any A,B \in \mathcal{I} with |A| < |B|:
    • If |A| \le 1, we can always add an element from B\setminus A (since any single element is independent, and |B| \ge 2 means at least one element is available).
    • If A = \{x,y\} (size 2), then |B| must be 3, so B = \{1,2,3\}. Since |A|=2, there is at least one element in B\setminus A; adding it gives a set of size 3 which is either in \mathcal{I} (if it is \{1,2,3\}) or of size \le 2 (still independent).
NoteProblem A3

Let G be a connected graph with n vertices and m edges. In the graphic matroid M(G), a subset of edges is independent iff it contains no cycle.

  1. What is the rank of M(G)? (The size of a maximal independent set.)
  2. For G = K_4, list one base and one circuit (minimal dependent set) of M(G).
  1. The rank of M(G) is n-1 (size of a spanning tree).
  2. For K_4, one base is any spanning tree of 3 edges (e.g., edges (1,2),(2,3),(3,4)). One circuit is any cycle of 3 edges (e.g., (1,2),(2,3),(1,3)).
NoteProblem A4

Let S = \{e_1, e_2, e_3, e_4, e_5\} with weights w(e_1)=10, w(e_2)=8, w(e_3)=6, w(e_4)=4, w(e_5)=2. Let \mathcal{I} = \{X \subseteq S : |X| \le 2\} (a uniform matroid of rank 2).

  1. Run the greedy algorithm on this weighted matroid. What set does it return?
  2. List all independent sets. Which one has maximum total weight? Does greedy return it?
  3. Suppose we instead used a minimum-weight greedy (pick smallest weight first, add if independent). What set would it return?

  1. Greedy sorts by decreasing weight: e_1(10), e_2(8), e_3(6), e_4(4), e_5(2). It adds e_1 (weight 10), then e_2 (weight 8) since \{e_1,e_2\} has size 2 \le 2 and is independent. It then skips e_3, e_4, e_5 because \{e_1,e_2,e_3\} has size 3 > 2. Output: \{e_1, e_2\} (total weight 18).

  2. Independent sets: all subsets of size \le 2. The maximum-weight size-2 set is \{e_1, e_2\} (weight 18). Yes, greedy returns the maximum-weight independent set.

  3. Minimum-weight greedy sorts by increasing weight: e_5(2), e_4(4), e_3(6), e_2(8), e_1(10). It adds e_5 (independent), then e_4 (\{e_5,e_4\} has size 2 \le 2, independent), then skips the rest. Output: \{e_4, e_5\} (total weight 6).

However, this is not the minimum-weight independent set overall — \emptyset (weight 0) and \{e_5\} (weight 2) are independent with smaller weight. The greedy algorithm (whether max or min) always returns a basis (size = rank). Max-weight greedy gives the max-weight basis; min-weight greedy gives the min-weight basis. It cannot return a non-maximal set like \{e_5\} because it keeps adding elements as long as independence allows.