maximal length of an augmenting path in a flow network bipartite graph

Question

Disclaimer: This is a homework question.

The question:

let $G=(V,E)$ be a bipartite graph with vertex partition $V=V_1\cup V_2$, and let $N$ be its corresponding flow network in the reduction to the maximum matching problem.

What is the maximal length (in edges) of an augmenting path found in $N$ during the execution of Ford-Fulkerson? The answer should be a function of $|V_1|$ and $|V_2|$ .

--

When they say $N$ corresponding flow network, I guess they meant they added vertex s to all $V_1$ (connected by edges), and vertex t to all $V_2$ (connected by edges), because that is what we did in class.

EDIT: this question was unclear because I didn't know if an augmented path is a simple path or not, but it was later clarified that it is in this question.

Answer 1

If I understand correctly, the question considers all possible bipartite graphs over $(V_1,V_2)$ and asks to find the longest possible augmenting path for all these bipartite graphs. If so, the longest path is an alternating one like $s \rightarrow v_1 \rightarrow u_1 \rightarrow \cdots \rightarrow v_\ell \rightarrow u_\ell \rightarrow t$ where $v_i$'s are in $V_1$ and $u_i$'s are in $V_2$ and $\ell$ is at most $\min\{|V_1|, |V_2|\}$. Thus, the maximum possible length is $2\min\{|V_1|, |V_2|\} + 1$.