0
$\begingroup$

In a bipartite graph, the size of a maximum matching equals the size of the minimum vertex cover.

I want to prove above theorem using max-flow-min-cut theorem. So I am trying to find the relationship between min-cut and min vertex cover, do you think |min-cut| = |min-vertex-cover|? If so, any proof for it?

$\endgroup$
  • $\begingroup$ The max-flow min-cut theorem applies to a flow network with a source, a sink, and edge weights. A bipartite graph does not have those, by default. So as it stands, your equality does not even make sense. $\endgroup$ – Misha Lavrov Oct 3 '17 at 5:21
  • $\begingroup$ what if I constructed new graph G` by adding a source and sink vertex to bipartite graph, such that flow from source to any vertex is zero, and any vertex to sink is zero. and all capacity of the new construction is 1. $\endgroup$ – ajayramesh Oct 3 '17 at 14:31
1
$\begingroup$

I think your confusion lies in the correspondence between flows in a bipartite graph and maximum matchings. To find a maximum matching, consider the bipartite graph $G=(L,R,E)$ where $L$ is the set of vertices on the left side of the bipartition and $R$ is the set on the right side. Now, add a new vertex $s$ and a directed edge $(s,\ell)$ for each $\ell \in L$. Also, add a new vertex $t$ and a directed edge $(r,t)$ for each $r\in R$. Orient all of the edges in $E$ towards $T$ and set every edge in your new graph to have capacity 1. Below is an example of the resulting graph: bipartite matching

Solve for max flow on this graph with $s$ as your source and $t$ as your terminal. The saturated edges (which were originally in $E$) in a max flow for this graph correspond to the edges in a maximum matching, and the flow value is the size of said matching (convince yourself! i.e. assume you have a max matching that is bigger/ smaller than the flow value and see what that implies).

Now, the flow value also corresponds to the size of a minimum vertex cover, but NOT NECESSARILY the size of a minimum cut. This is because we added a source and a sink node, and the edges from $s$ to $L$ and from $R$ to $t$ which could now be part of our min cut in this new graph. Hope this clears up some confusion.

$\endgroup$
0
$\begingroup$

If I'm interpreting your question and comment correctly, you mean a minimum set of edges such that their deletion would make the graph disconnected. Consider the path with $4$ vertices, which is bipartite. You'll need at least two vertices to hit every edge, but deleting any edge will make the graph disconnected, so $|\mathrm{min\;cut}|\neq|\mathrm{min\;vertex\;cover}|$.

$\endgroup$
0
$\begingroup$

Contrary to the suggestions of the other users, I believe this can be proved (the counterexample provided does not address the OP's problem as OP clarified it in the comments).

Let the original graph be $G$, the new graph be $G^\prime$, the vertices on the left be $V_1$, the vertices on the right be $V_2$, and the source and sink be $s$ and $t$ respectively.

$|\text{min cut}| \leq |\text{min vertex cover}|$:

Let $C_1 \cup C_2$, where $C_1 \subseteq V_1, C_2 \subseteq V_2$, be the smallest vertex cover. Consider the following cut:

$S = \{s\} \cup (V_1 \setminus C_1 ) \cup C_2$

Then

$\bar{S} = \{t\} \cup C_1 \cup (V_2 \setminus C_2)$

Note that none of the arcs from $V_1$ to $V_2$ are present in the cut. We can see this as follows. If an arc starts from a vertex in $V_1$ inside the vertex cover, then it is not in $S$ in the first place. If an arc starts from a vertex in $V_1$ not in the vertex cover, then it must end in a vertex in $V_2$ in the cover (otherwise we would not have a vertex cover). Therefore, the arc must not be in the cut, since it connects two vertices within $S$.

As a result, the only arcs in the cut are those from $\{s\}$ to $C_1$ and from $C_2$ to $\{t\}$. The size of this cut is $|C_1 \cup C_2|$, or the size of the minimum vertex cover. Therefore, the size of the min cut is at most the size of the min vertex cover.

$|\text{min cut}| \geq |\text{min vertex cover}|$:

Let the minimum cut be $(S,\bar{S})$. We express the cut as follows:

$S = \{s\} \cup (V_1 \setminus C_1 ) \cup C_2$

$\bar{S} = \{t\} \cup C_1 \cup (V_2 \setminus C_2)$

where $C_1 \subseteq V_1$ and $C_2 \subseteq V_2$. Clearly, the arcs inside this cut consist of all the arcs from $\{s\}$ to $C_1$, from $V_2 \cap C_2$ to $\{t\}$, and from $V_1 \setminus C_1$ to $V_2 \setminus C_2$.

Consider the set $C_1 \cup C_2$. We may expand this set to a vertex cover by adding all the vertices of $V_1 \setminus C_1$ for which an arc from it to $V_2 \setminus C_2$ exists. Obviously the size of this set is the same as the size of the min cut. So the size of the minimum vertex cover is at most the size of the minimum cut and we are done.

$\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.