Skip to main content
Computer Science

Return to Answer

edited body
Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

First of all, you have to show that $V_C$ is a vertex cover. This is because any edge touching a leaf also touches an internal node.

Next, we show that the DFS tree has a matching of size at least $|V_C|/2$. Since each vertex cover must contain at least one vertex from each edge in the matching (since any one vertex covers only one edge from the matching), this shows that the minimum vertex cover has size at least $|V_C|/2$, so we get a 2-approximation algorithm.

It remains to show that any tree $T$ has a matching of size at least $I(T)/2$, where $I(T)$ is the number of internal node. The proof is by induction on $|T|$. If $T$ contains one vertex then $I(T)=0$ and so there is nothing to prove. Now suppose that the tree contains a root $r$ and subtrees $T_1,\ldots,T_m$$T_1,\ldots,T_n$. Let $r_1$ be the root of $T_1$, and let $S_1,\ldots,S_m$ be the subtrees of $T_1$. The matching we are going to construct consists of matchings in $S_1,\ldots,S_m,T_2,\ldots,T_n$ together with the edge $(r,r_1)$ (you can check that this is indeed a matching). This matching contains at least $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2$ many edges. We obtained the forest $S_1,\ldots,S_m,T_2,\ldots,T_n$ by removing two vertices $r,r_1$, so $I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n) = I(T)-2$. This completes the proof since $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2 = 1+(I(T)-2)/2 = I(T)/2$.

First of all, you have to show that $V_C$ is a vertex cover. This is because any edge touching a leaf also touches an internal node.

Next, we show that the DFS tree has a matching of size at least $|V_C|/2$. Since each vertex cover must contain at least one vertex from each edge in the matching (since any one vertex covers only one edge from the matching), this shows that the minimum vertex cover has size at least $|V_C|/2$, so we get a 2-approximation algorithm.

It remains to show that any tree $T$ has a matching of size at least $I(T)/2$, where $I(T)$ is the number of internal node. The proof is by induction on $|T|$. If $T$ contains one vertex then $I(T)=0$ and so there is nothing to prove. Now suppose that the tree contains a root $r$ and subtrees $T_1,\ldots,T_m$. Let $r_1$ be the root of $T_1$, and let $S_1,\ldots,S_m$ be the subtrees of $T_1$. The matching we are going to construct consists of matchings in $S_1,\ldots,S_m,T_2,\ldots,T_n$ together with the edge $(r,r_1)$ (you can check that this is indeed a matching). This matching contains at least $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2$ many edges. We obtained the forest $S_1,\ldots,S_m,T_2,\ldots,T_n$ by removing two vertices $r,r_1$, so $I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n) = I(T)-2$. This completes the proof since $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2 = 1+(I(T)-2)/2 = I(T)/2$.

First of all, you have to show that $V_C$ is a vertex cover. This is because any edge touching a leaf also touches an internal node.

Next, we show that the DFS tree has a matching of size at least $|V_C|/2$. Since each vertex cover must contain at least one vertex from each edge in the matching (since any one vertex covers only one edge from the matching), this shows that the minimum vertex cover has size at least $|V_C|/2$, so we get a 2-approximation algorithm.

It remains to show that any tree $T$ has a matching of size at least $I(T)/2$, where $I(T)$ is the number of internal node. The proof is by induction on $|T|$. If $T$ contains one vertex then $I(T)=0$ and so there is nothing to prove. Now suppose that the tree contains a root $r$ and subtrees $T_1,\ldots,T_n$. Let $r_1$ be the root of $T_1$, and let $S_1,\ldots,S_m$ be the subtrees of $T_1$. The matching we are going to construct consists of matchings in $S_1,\ldots,S_m,T_2,\ldots,T_n$ together with the edge $(r,r_1)$ (you can check that this is indeed a matching). This matching contains at least $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2$ many edges. We obtained the forest $S_1,\ldots,S_m,T_2,\ldots,T_n$ by removing two vertices $r,r_1$, so $I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n) = I(T)-2$. This completes the proof since $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2 = 1+(I(T)-2)/2 = I(T)/2$.

Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

First of all, you have to show that $V_C$ is a vertex cover. This is because any edge touching a leaf also touches an internal node.

Next, we show that the DFS tree has a matching of size at least $|V_C|/2$. Since each vertex cover must contain at least one vertex from each edge in the matching (since any one vertex covers only one edge from the matching), this shows that the minimum vertex cover has size at least $|V_C|/2$, so we get a 2-approximation algorithm.

It remains to show that any tree $T$ has a matching of size at least $I(T)/2$, where $I(T)$ is the number of internal node. The proof is by induction on $|T|$. If $T$ contains one vertex then $I(T)=0$ and so there is nothing to prove. Now suppose that the tree contains a root $r$ and subtrees $T_1,\ldots,T_m$. Let $r_1$ be the root of $T_1$, and let $S_1,\ldots,S_m$ be the subtrees of $T_1$. The matching we are going to construct consists of matchings in $S_1,\ldots,S_m,T_2,\ldots,T_n$ together with the edge $(r,r_1)$ (you can check that this is indeed a matching). This matching contains at least $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2$ many edges. We obtained the forest $S_1,\ldots,S_m,T_2,\ldots,T_n$ by removing two vertices $r,r_1$, so $I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n) = I(T)-2$. This completes the proof since $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2 = 1+(I(T)-2)/2 = I(T)/2$.