Difficulty in understanding the proof of the lemma : “Matroids exhibit the optimal-substructure property”

Question

I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma I give a brief description of the possible prerequisites for the lemma.

---

Let $M=(S,\ell)$ be a weighted matroid where $S$ is the ground set and $\ell$ is the family of subsets of $S$ called the independent subsets of $S$. Let $w:S\rightarrow\mathbb{R}$ be the corresponding weight function ($w$ is strictly positive).

Let us have an algorithm which finds an optimal subset of $M$ using greedy method as:

$\text{G}{\scriptstyle{\text{REEDY}}}(M,w):$

$1\quad A\leftarrow\phi$

$2\quad \text{sort $S[M]$ into monotonically decreasing order by weight $w$}$

$3\quad \text{for each $x\in S[M]$, taken in monotonically decreasing order by weight $w(x)$}$

$4\quad\quad \text{do if $A\cup\{x\} \in \ell[M]$}$

$5\quad\quad\quad\text{then $A\leftarrow A\cup \{x\}$}$

$6\quad \text{return $A$}$

---

I was having a problem in understanding a step in the proof of the lemma below.

Lemma: (Matroids exhibit the optimal-substructure property)

Let $x$ be the first element of $S$ chosen by $\text{G}{\scriptstyle{\text{REEDY}}}$ for the weighted matroid $M = (S, \ell)$. The remaining problem of finding a maximum-weight independent subset containing $x$ reduces to finding a maximum-weight independent subset of the weighted matroid $M' = (S', \ell')$, where

$S' = \{y\in S:\{x,y\}\in \ell\}$ ,

$\ell' = \{В \subseteq S - \{x\} : В \cup \{x\} \in \ell\}$ ,

and the weight function for $M'$ is the weight function for $M$, restricted to $S'$. (We call $M'$ the contraction of $M$ by the element $x$.)

Proof:

1. If $A$ is any maximum-weight independent subset of $M$ containing $x$, then $A' = A - \{x\}$ is an independent subset of $M'$.

2. Conversely, any independent subset $A'$ of $M'$ yields an independent subset $A = A'\cup\{x\}$ of $M$.

3. We have in both cases $w(A) = w(A') + w(x)$.

4. Since we have in both cases that $w(A) = w(A') + w(x)$, a maximum-weight solution in $M$ containing $x$ yields a maximum-weight solution in $M'$, and vice versa. ■

---

I could understand $(1),(2),(3)$. But I could not get how the line $(4)$ was arrived in the proof from $(1),(2),(3)$, especially the part in bold-italics. Could anyone please make it clear to me?

Answer 1

The adjective "maximum-weight" should not appear in item (1) in that proof of the lemma. This is a minor bug of that famous book.

To be fully clear, item (1) should have been the following.

1. If $A$ is any independent subset of $M$ containing $x$, then $A' = A - \{x\}$ is an independent subset of $M'$.

With item (1) corrected, item (4) follows naturally from item (1), (2) and (3). Here is more detail.

---

"A maximum-weight solution in $M$ containing $x$ yields a maximum-weight solution in $M'$."

Note that "solution" is just a shorthand for "independent set". Let us prove the proposition above.

Suppose $A$ is a maximum-weight solution in $M$. Then $A$ yields $A'=A-\{x\}$, which is a solution in $M'$ according to item (1). (The previous version of item (1) works as well.)

Given any solution $B'$ in $M'$, let $B=B'\cup\{x\}$, which is a solution in $M$ according to item (2).

Item (3) tells us $w(A)=w(A')+w(x),$ and $w(B)=w(B')+w(x).$ Since $A$ has maximum weight in $M$, we have $w(A)\ge w(B)$, i.e., $$w(A')+w(x)\ge w(B')+w(x).$$ Cancelling $w(x)$ from both sides, we obtain $$w(A')\ge w(B'),$$ which says $A'$ is a maximum-weight solution in $M'$. $\checkmark$

---

A maximum-weight solution in $M'$ yields a maximum-weight solution in $M$ containing $x$.

The other direction, as stated above, can be proved similarly. Here is the proof.

Suppose $B'$ is a maximum-weight solution in $M'$. Then $B'$ yields $B=B'\cup\{x\}$, which is a solution in $M$ according to item (2).

Given any solution $A$ in $M$, let $A'=A-\{x\}$, which is a solution in $M'$ according to (the corrected version of) item (1).

Since $B'$ has maximum weight in $M'$, we have $w(B')\ge w(A')$. Adding $w(x)$ to both sides, we obtain, $$w(B')+w(x)\ge w(A')+w(x).$$

Item (3) tells us $w(A)=w(A')+w(x),$ and $w(B)=w(B')+w(x).$ So the inequality above is the same as $$w(B)\ge w(A),$$

which says $B$ is a maximum-weight solution in $M$. $\checkmark$

Answer 2

For convenience:

$$W(P) = \sum_{p\in P} \omega (p)$$

First case: $A$ is max. independent set of $M$

Now let's assume $A'$ wasn't the max. independent set of $M'$. Thus another max. independent set $H\in l'$ must exist. $$W(A') < W(H)$$ Since every independent set in $l'$ has a corresponding set in $l$ including $x$ we can conclude $H\cup\{x\}\in l$ and hence: $$W(A') + \omega(x)< W(H)+\omega(x) \Rightarrow W(A'\cup\{x\}) < W(H\cup\{x\})$$ But $A'\cup\{x\} = A$ which is a contradiction since $A$ is the max. independent set of $M$.

The other way around is a bit trickier.
Second case: $A'$ is max. independent set of $M'$.

Now we assume $A$ wasn't the max. independent set of M. This would imply the existence of a set $H\in l$ with $W(H) > W(A)$. Now we can apply the hereditary property to $A$ and conclude that $\{x\}\in l$. To $H$ and $Z = \{x\}$ we can now apply the independent set exchange property repeatedly to augment $Z$ to $Z'$ until it contains all elements in $H$ except its smallest. Thus
$$Z' = Z \cup H - \{\text{argmin}_{h\in H}\{\omega(h)\}\}$$ $$W(Z') \geq W(H)$$. Since $Z'$ contains $x$ and $$W(Z')>W(A) \Rightarrow W(Z'-\{x\}) > W(A')$$ we have a contradiction (we assumed A' was max. set of M').