# 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.
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.


**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