1. From Wikipedia, in a bipartite graph, when given a maximum matching, there is way to construct a vertex cover of the same size as the matching:

    Consider a bipartite graph where the vertices are partitioned into left (L) and right (R) sets. Suppose there is a maximum matching which partitions the edges into those used in the matching ($E_m$) and those not ($E_0$). Let T consist of all unmatched vertices from L, as well as all vertices reachable from those by going left-to-right along edges from $E_0$ and right-to-left along edges from $E_m$. This essentially means that for each unmatched vertex in L, we add into T all vertices that occur in a path alternating between edges from $E_0$ and $E_m$.

    Then $(L \setminus T) \cup (R \cap T)$ is a minimum vertex cover. Intuitively, vertices in T are added if they are in R and subtracted if they are in L to obtain the minimum vertex cover. Thus, the Hopcroft–Karp algorithm for finding maximum matchings in bipartite graphs may also be used to solve the vertex cover problem efficiently in these graphs.

    I am not sure how $T$ is constructed, and cannot picture $T$ even after reading the sentences in bold. So I wonder how to understand those sentences?

  2. Conversely, in a bipartite graph, when given a minimum vertex cover, what is some way to construct a matching of the same size as the vertex cover?


PS: This is from my comment on Fixee's reply.


Your Answer

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

Browse other questions tagged or ask your own question.