---
# System prepended metadata

title: CS 577 Discussion QA (Week 10)

---

# CS 577 Discussion QA (Week 10)

## QuickSelect on Matrix
Q: for problem 1 can you always assume that i1 > i0 and j1 >j0?
A: It has to, if less, does not make sense. Implied by monotonicity of matrix

Q: How can we achieve $O(n)$ if there are possibly $O(n^2)$ in the range?
We only compute the start and end position of candidate elements in the range.
![](https://i.imgur.com/R8d29oX.png)
To sample from an element in one row, we only need constant time. 
Since there are only $n$ rows, we can do sampling in $O(n)$ without labeling all the elements in the range.


## Uniqueness Of Max Flow
Q: Go overProof of Question 2
A: Rough Idea of the proof

Part B follows directly from Part A
Graph G has multiple distinct iff residual network has a directed cycle with positive residue capacity (Goes both direction)

### Claim 1: If the residual has a positive residual cycle, there exists distinct max flow
Assume $C$ is the cycle in the residual graph, consist of $f_{e1}, f_{e2}, f_{e3}, f_{e4}$.
Idea: push positive flow through the cycle by exactly 1 unit. 
Since it is a cycle, the flow is still feasible since each nodes receive exactly 1 more unit of input flow and 1 more unit of output flow. Besides, the flow is for sure different.

**Remark** The value of the flow still stays the same. So the flow remains a maximum flow.

---
Q: Do we need consider backward/forward edge?
A: Can be both forward/backward. Backward flow just corresponds to decrement the actual flow in the original graph.

Q: All the edges need to be forward/backward?
A: It does not matter if the edge is forward or backward

**Remark** The cycle always consists of some backward edge/ some foward edge since the original graph is acyclic. The "pushing" action actually corresponds to some re-routing of flow in the original graph.

Q: For Claim 1 of part(a), is it saying we can add 1 to all edges or only edges in the cycle?
A: We only add 1 to edges within the cycle.

---

### Claim 2: Given two discint max flow, there exists a positive residual cycle corresponds to one of the flow

Given $Val(f) = Val(f')$, where $f$, $f'$ are two distinct max flow. Define $\Delta_e = f_e' - f_e^*$. 

**Lemma** show that $\Delta_e$ satisfies flow-conservation.

![](https://i.imgur.com/2rl9WJ0.png)


**Lemma** There exists an edge $e$ s.t $\Delta_e \neq 0$.

With the two lemma, we can start from the edge corresponding to a non-zero $\Delta_e$. Due to flow conservation, we can always find another edge following the starting edge which also has a non-zero $\Delta_e$. Doing that iteratively. Since there are only finnite many edges, the path we trace through always end up with a cycle.

Q: Does FF algorithm also works for cyclic graph?
A: Not 100% sure. But should still be correct. Just implementation a bit more tricky. 

Q: Understand that we can always follow edges with $\Delta_e \neq 0$ to get a series of vertices. Why do them neccesarily form a cycle. 
A: Due to flow conservation, this tracing process never ends. Since we only have finite amount of edges in the graph, we always end up visiting some vertices twice - which then gives us a cycle. 

Q: In the discussion video, the TA shows two cases: △e > 0 and △e < 0. Can you explain how these two cases form different cycles?
A: Notice that we define $\Delta_e = f_e' - f_e^*$. When $\Delta_e > 0$, we have $f_e^' > f_e^*$. Thus, we have positive capacity in the residual graph corresponding to $f^*$. If $\Delta_e < 0$, we have cycle in the residual graph corresponding to $f'$.


### Polynomial Algorithm