3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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$

$\endgroup$
5
  • $\begingroup$ Can you please tell me the meaning of the convention about "yielding rule" :$B'\mapsto B'\cup\{x\}$ (and $A\mapsto A-\{x\}$) which you have mentioned in the last part. (I understood from your way of answering the first direction, as how to symmetrically work in the other direction, we shall assume a max-weight independent set $A'$ of $M'$ and again an arbitrary independent set $B'$ of $M'$ and then proceed in a similar manner to show $w(A)\geq w(B)$ ) $\endgroup$ – Abhishek Ghosh Jul 7 '20 at 14:24
  • 1
    $\begingroup$ @AbhishekGhosh Please check my update. $\endgroup$ – John L. Jul 7 '20 at 14:51
  • $\begingroup$ thank you for you help... $\endgroup$ – Abhishek Ghosh Jul 7 '20 at 14:55
  • 1
    $\begingroup$ @AbhishekGhosh Apparently the other answer in its second case is proving something different from the lemma. There is no need to read that part. $\endgroup$ – John L. Jul 7 '20 at 15:22
  • $\begingroup$ Okay thanks for the guidance as well. $\endgroup$ – Abhishek Ghosh Jul 7 '20 at 16:06
2
$\begingroup$

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').

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.