Based on my readings on the algorithm, my understanding is that the improvement of the feasible vertex labeling in step 2. is supposed to be such that $G_l subset G_l’$. The part I’m getting stuck on is that it seems to me that it is possible for there to be an edge $xy$ in $G_l$ with $y in T$ but $x not in S$ resulting in the fact that $$ l'(x) + l'(y) = l(x) + (l(y) + alpha_l) not = w(xy) $$ and so $ xy not in G_l’$ and $G_l not subset G_l’$. Can anyone point out where I’m going wrong?
Asked By : Isaac Kleinman
Answered By : Sasho Nikolov
- all edges in $M$ remain edges of $G_{l’}$
- we don’t remove vertices from $S$ and $T$ until we increase the size of the matching $M$, at which point $S$ and $T$ are reset (step 1); so the size of $S$ and $T$ is monotonically increasing until the size of $M$ is increased by 1
- after updating the labels to $l’$, the size of $T$ is increased by at least 1 in the next step
What can you conclude from this? The size of the matching $M$ never decreases. At each iteration we either increase the size of $T$, or we update the labels, which will cause us to increase the size of $T$ in the next iteration. So after $2n$ iterations, the size of $T$ will be $n$. Since $T$ cannot grow anymore, we will have to increase the size of $M$. But the size of $M$ is at most $n$, so the algorithm will finish after at most $O(n^2)$ iterations. An iteration can be executed in time $O(m)$, so the total running time is bounded by $O(n^2m)$. BTW the sets $S$ and $T$ are a bit mysterious in this description of the algorithm. Here is how we usually think about them. Orient all edges in $G_l$ as follows: the edges in $M$ go from $Y$ to $X$ and all other edges go from $X$ to $Y$. Then $x$ is an unmatched vertex, $T$ is computed to be the set of vertices in $Y$ reachable from $x$ by a directed path, and $S$ is the set of vertices in $X$ reachable from $x$ by a directed path. If $T$ contains an unmatched vertex, we have found an odd-length alternating path, and we can augment the matching (increase its size by reversing the direction of the edges along the path). Otherwise, we can change $l$ so that the size of $T$ increases.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7341
