Skip to main content
added 10 characters in body
Source Link
John K.
  • 17.1k
  • 3
  • 43
  • 67

I have no clue about how the values in the other two lemmas are brought up.

The how is this: What are the values $a$ and $b$ such that $ab = n$ and $O(a + b)$ is minimized?

The answer is $\sqrt n$, and that value is chosen in the argument above for that precise reason.

After $\sqrt n$ phases, we know that the BFS layer graph must have at least $\sqrt n$ many layers, which means that there is a layer with at most $\sqrt n$ many vertices. But if there is a layer with at most $\sqrt n$ many vertices, then the $s$-$t$-cut is at most $\sqrt n$ in this graph.

To see this: Let $L_i$ be a layer with $\leq \sqrt n$ many vertices. And let $L_i^\leftarrow$ be the set of vertices in $L_i$ with exactly one in-edge, and let $L_i^\rightarrow$ be the set ofall other vertices in $L_i$ with(they all have exactly one out-edge. Notice that $L_i^\leftarrow, L_i^\rightarrow$ partitions $L_i$ since $G$ is a unit-capacity network). Notice that $L_i^\leftarrow, L_i^\rightarrow$ partitions $L_i$.

Now, let $A$ be the set of vertices in layers $L_j$ for $j < i$, plus $L_i^\leftarrow$. You should be able to draw a figure that convinces you of the fact that the capacity of the cut $A,B$ is at most $\sqrt n$.

This implies that $v(f) \geq v(f^*) - \sqrt n$.

But then, after an additional $\sqrt n$ phases, we have reached $v(f^*)$.

Hence, after at most $2\sqrt n$ phases, we have reached the optimal flow. Since each phase can be performed in time $O(m)$, the algorithm runs in time $O(\sqrt n)$.

I have no clue about how the values in the other two lemmas are brought up.

The how is this: What are the values $a$ and $b$ such that $ab = n$ and $O(a + b)$ is minimized?

The answer is $\sqrt n$, and that value is chosen in the argument above for that precise reason.

After $\sqrt n$ phases, we know that the BFS layer graph must have at least $\sqrt n$ many layers, which means that there is a layer with at most $\sqrt n$ many vertices. But if there is a layer with at most $\sqrt n$ many vertices, then the $s$-$t$-cut is at most $\sqrt n$ in this graph.

To see this: Let $L_i$ be a layer with $\leq \sqrt n$ many vertices. And let $L_i^\leftarrow$ be the set of vertices in $L_i$ with exactly one in-edge, and let $L_i^\rightarrow$ be the set of vertices in $L_i$ with exactly one out-edge. Notice that $L_i^\leftarrow, L_i^\rightarrow$ partitions $L_i$ since $G$ is a unit-capacity network.

Now, let $A$ be the set of vertices in layers $L_j$ for $j < i$, plus $L_i^\leftarrow$. You should be able to draw a figure that convinces you of the fact that the capacity of the cut $A,B$ is at most $\sqrt n$.

This implies that $v(f) \geq v(f^*) - \sqrt n$.

But then, after an additional $\sqrt n$ phases, we have reached $v(f^*)$.

Hence, after at most $2\sqrt n$ phases, we have reached the optimal flow. Since each phase can be performed in time $O(m)$, the algorithm runs in time $O(\sqrt n)$.

I have no clue about how the values in the other two lemmas are brought up.

The how is this: What are the values $a$ and $b$ such that $ab = n$ and $O(a + b)$ is minimized?

The answer is $\sqrt n$, and that value is chosen in the argument above for that precise reason.

After $\sqrt n$ phases, we know that the BFS layer graph must have at least $\sqrt n$ many layers, which means that there is a layer with at most $\sqrt n$ many vertices. But if there is a layer with at most $\sqrt n$ many vertices, then the $s$-$t$-cut is at most $\sqrt n$ in this graph.

To see this: Let $L_i$ be a layer with $\leq \sqrt n$ many vertices. And let $L_i^\leftarrow$ be the set of vertices in $L_i$ with exactly one in-edge, and let $L_i^\rightarrow$ be all other vertices in $L_i$ (they all have exactly one out-edge since $G$ is a unit-capacity network). Notice that $L_i^\leftarrow, L_i^\rightarrow$ partitions $L_i$.

Now, let $A$ be the set of vertices in layers $L_j$ for $j < i$, plus $L_i^\leftarrow$. You should be able to draw a figure that convinces you of the fact that the capacity of the cut $A,B$ is at most $\sqrt n$.

This implies that $v(f) \geq v(f^*) - \sqrt n$.

But then, after an additional $\sqrt n$ phases, we have reached $v(f^*)$.

Hence, after at most $2\sqrt n$ phases, we have reached the optimal flow. Since each phase can be performed in time $O(m)$, the algorithm runs in time $O(\sqrt n)$.

Source Link
John K.
  • 17.1k
  • 3
  • 43
  • 67

I have no clue about how the values in the other two lemmas are brought up.

The how is this: What are the values $a$ and $b$ such that $ab = n$ and $O(a + b)$ is minimized?

The answer is $\sqrt n$, and that value is chosen in the argument above for that precise reason.

After $\sqrt n$ phases, we know that the BFS layer graph must have at least $\sqrt n$ many layers, which means that there is a layer with at most $\sqrt n$ many vertices. But if there is a layer with at most $\sqrt n$ many vertices, then the $s$-$t$-cut is at most $\sqrt n$ in this graph.

To see this: Let $L_i$ be a layer with $\leq \sqrt n$ many vertices. And let $L_i^\leftarrow$ be the set of vertices in $L_i$ with exactly one in-edge, and let $L_i^\rightarrow$ be the set of vertices in $L_i$ with exactly one out-edge. Notice that $L_i^\leftarrow, L_i^\rightarrow$ partitions $L_i$ since $G$ is a unit-capacity network.

Now, let $A$ be the set of vertices in layers $L_j$ for $j < i$, plus $L_i^\leftarrow$. You should be able to draw a figure that convinces you of the fact that the capacity of the cut $A,B$ is at most $\sqrt n$.

This implies that $v(f) \geq v(f^*) - \sqrt n$.

But then, after an additional $\sqrt n$ phases, we have reached $v(f^*)$.

Hence, after at most $2\sqrt n$ phases, we have reached the optimal flow. Since each phase can be performed in time $O(m)$, the algorithm runs in time $O(\sqrt n)$.