# [Public Notes] Isolating cut
## Standard notations
* $\tilde O$ hides $polylog(n)$.
**Min (S,T)-cut:**
* For any non-empty disjoint $S,T\subset V$, vertex set $C$ is an $(S,T)$-cut if $S\subseteq C$ but $T\cap C=\emptyset.$
* Weight/value of a cut $C$ is $πΏ(C)=β_{πβπΈ(C,π\setminus C)} π€(π)$
* $(S,T)$-mincut:= $(S,T)$-cut with min weight
## 1. Isolating cut framework
### 1.1 Input/Output
**INPUT:**
* $G=(V,E,w)$: *Undirected* graph with positive integral weights $π€:πΈβπ_+$
* $T\subseteq V$: called **terminal** set
**Definition:** $\forall v\in T$, a **$v$-isolating cut** (w.r.t. $T$) is a $(v, T\setminus v)$-cut.
**OUTPUT:** $\forall v$, a **min $v$-isolating cut** :=a $v$-isolating cut with minimum weight.
*Remark:* It will follow from the prove below that there exist **disjoint** isolating cuts, so the output size is linear.
**Naive algorithm (warm-up):**
* Connect $s$ to $v$ and $t$ to other terminals with infinite weights.
* A $v$-isolating cut is an st-cut.
* The min $v$-isolating cut is the min st-cut.
### 1.2 Maxflow-time Algorithm [LPβ21,AKTβ21]
The algorithm below takes maxflow time, which is currently $m^{1+o(1)}$. The algorithm is due to Li and Panigrahi [LP'21] and, independently, Abboud, Krauthgamer, Trabelsi [AKT'21].
---
**Algorithm: IsoCut($G=(V,E,w), T\subseteq V$)**
**Step 1: Get "isolating component" $U_v$ via "group cuts"**
**Def:** For $i=1...\log(|T|)$, define $T_i\subset T$ so that for every distinct $u,v\in T$, we have $u\in T_i$ and $v\not\in T_i$ for some $i$.
* E.g., write terminal with $\log(|T|)$ bits.
* $T_i$=set of terminals whose $i^{th}$ bit is 0.
**For $i=1...\log(|T|)$:**
1. Compute $(T_i,T\setminus T_i)$-mincut $C_i$ in maxflow time.
* Connect $s$ to nodes in $T_i$ and $t$ to $T\setminus T_i$ with **$\infty$** weight.
2. Delete edges in the mincut.
We will sometimes call mincuts from this step "group cuts".
![](https://i.imgur.com/I3XdLaQ.png)
**Remarks:**
* **Observe:** No distinct $u,v\in T$ in the same connected component.
* **Def:** Let $U_v\subseteq V$ be the component containing $v\in V$.
* **Isolating Cut Lemma:** Exists $v$-isolating cut $S_π£β U_π£$.
**Proof:** Later.
![](https://i.imgur.com/VrqzevF.png)
**Step 2: Work on each component $U_v$ separately.**
* $πΊ_π£$ := contract $π\setminus π_π£$ into sink $π‘_π£$.
* Compute $(v,t_v)$ mincut.
![](https://i.imgur.com/16FlO2q.png)
---
### 1.3 Time Complexity (Easy)
Step 1: $O(\log |T|)$ maxflow computation
Step 2: If maxflow takes $O(m^\alpha)$ time, then step 2 takes $O(m^\alpha)$ time.
* Because each edge participates in $\leq 2$ maxflow computation.
### 1.4 Proof of Isolating Cut Lemma #1 (using cut properties)
* Fix any terminal $v\in T$
* $S_v$ := minimum $v$-isolating cut that is *minimal* in the sense that any $S'_v\subsetneq S_v$ that contains $v$, $\delta(S'_v)>\delta(S_v)$.
* $C$ := any group cut from step 1. Assume w.l.o.g. $v\in C$.
* Assume for contradiction: $S_v\not\subset C$. Thus, there exists $x\in S_v\setminus C$.
* The following two facts contradict each other (see the picture below).
1. $\delta(C\cap S_v)>\delta(S_v).$ From Picture (1), we can conclude that $a<c$.
2. $\delta(C\cup S_v)\geq \delta(C).$ From Picture (2), we can conclude that $a\geq c$.
![](https://i.imgur.com/qLllmXV.png)
### 1.5 Proof of Isolating Cut Lemma #2 (using submodularity)
**Definition:** A submodular function is a set function $f:2^{V}\rightarrow \mathbb{R}$ which satisfies one of the following equivalent conditions.
1. For every $X,Y\subseteq V$, $f(X)+f(Y)\geq f(X\cup Y) + f(X\cap Y).$
2. For every $X\subseteq Y\subseteq V$ and every $v\in V\setminus Y$, $f(X\cup \{v\})-f(X)\geq f(Y\cup \{v\})-f(Y).$
* This is called "diminishing return property"
---
**Claim:** The cut function $\delta$ is submodular.
**Proof:** See the picture below.
* $\delta(X\cup \{v\})-\delta(X)=y+z-x$ (see picture (1)).
* $\delta(Y\cup \{v\})-\delta(Y)=z-y-x$ (see picture (2)).
* So, the deminishing return property holds: $\delta(X\cup \{v\})-\delta(X)\geq \delta(Y\cup \{v\})-\delta(Y).$
**QED**
![](https://i.imgur.com/p5bUoSP.png)
---
**Proof of Isolating Cut Lemma:** Define $S_v$ and $C$ as in Section 1.4.
*Assume for contradiction:* $S_v\not\subset C$; so $S_v\cap C\neq S_v$.
1. By submodularity, $\delta(S_v)+\delta(C)\geq \delta(S_v\cup C) + \delta(S_v\cap C)$.
2. By minimality of $S_v$ and since $S_v\cap C\neq S_v$, $\delta(S_v)<\delta(S_v\cap C).$
3. (1) and (2) imply $\delta(C)>\delta(S_v\cup C)$, which contradicts the fact that $C$ is a minimum group cut in Step 1.
**QED**
**Remarks:**
* The proof above shows that the isolating cut technique is quite general. It works with submodular functions.
* The crucial property is in fact the "uncrossing property".
* For cut function, the uncrossing property is this: for any vertices $s$ and $t$, let $C\subset V$ be an $(s,t)$-mincut. Then, for any $u,v\in C$, there exists $C'\subset C$ that is a $(u, v)$-mincut.
* *Exercise:* The above property can be extended to set functions. It is an interesting exercise to prove that the isolating cut technique works for any symmetric fuction ($f(S)=f(V\setminus S)$) with the uncrossing property.
## 2. Steiner Mincut
**Problem Definition:**
* INPUT: Undirected weighted graph $G=(V,E,w)$ and terminal set $T\subseteq V$.
* OUTPUT: Minimum Stiner cut, where a cut $C\subseteq V$ is called *Steiner cut* if $T\cap C\neq \emptyset$ and $T\setminus C\neq \emptyset$.
![](https://i.imgur.com/gP6Gmfy.png)
**Note:** This generalizes maxflow and global mincut.
* When $|T|=2$, the problem is min st-cut (maxflow).
* When $T=V$, the problem is global mincut.
**Time:**
* Until recently, nothing better than computing maxflow $|T|$ times.
* Now: $\tilde O($maxflow time$)$ via isolating cut.
**Algorithm sketch:**
1. $C^*$:= optimal solution. Assume w.l.o.g. $|T\cap C^*|\leq |T\setminus C^*|.$
2. Suppose we know $k:=|T\cap C^*|$. (We will guess it as $k=2^i$.)
3. Sample $S\subset T$ where each $v\in T$ is in $S$ w.p. $1/k$.
4. With constant probability $|S\cap C^*|=1$ and $|S|\geq 2$.
5. So, the minimum $v$-isolating cut (with terminal set $S$) among all $v\in S$ is a mininmum Steiner cut.
## 3. Hypergraph global min-cut
INPUT: Hypergraph $G = (V, E)$ where each hyperedge $e β E$ is a subset of vertices.
* INPUT SIZE: $p:=\sum_{e\in E} |e|$.
OUTPUT: Global min-cut, i.e. nonempty $C\subset V$ that minimize the number of edges $e$ that overlaps with both $C$ and $V\setminus C$.
*Remark:* The technique below works for the weighted version, but let's focus on the unweighted version for simplicity.
RUNTIME:
* Until recently: $O(p+\lambda n^2)$ and $\tilde O(p+\min\{\lambda n^2, n^r, \sqrt{pn(m+n^{1.5})}\})$
* $n:=|V|$, $m:=|E|$, $r:=\max_{e\in E} |e|$, $\lambda$:= value of mincut.
* With isolating cut and almost-linear maxflow: $p^{1+o(1)}$.
**Algorithm sketch:**
1. $C^*$:= optimal solution. Assume w.l.o.g. $|C^*|\leq |V\setminus C^*|.$
2. Suppose we know $k:=|C^*|$. (We will guess it as $k=2^i$.)
3. Sample $S\subset V$ where each vertex $v$ is in $S$ w.p. $1/k$.
4. With constant probability $|S\cap C^*|=1$ and $|S|\geq 2$.
5. So, the minimum $v$-isolating cut (with terminal set $S$) among all $v\in S$ is a mininmum cut.
* Define isolating cuts in the same manner as in graphs.
**Claim 1:** A hypergraph $(S,T)$-mincut can be computed in maxflow time.
**Claim 2:** The isolating cut lemma holds for hypergraph. (Proof idea: Submodularity.)
**Exercise:** Prove the above two claims and that the algorithm sketched above returns the global mincut.
## 4. Vertex connectivity
INPUT: Unweighted graph $G = (V, E)$.
OUTPUT: Minimum vertex cut.
* A vertex partition $(L,C,R)$ is called a vertex cut if $N(L)\subseteq C$ and $N(R)\subseteq C$
* $N(L)$:= set of neighbor vertices of $L$ (excluding vertices in $L$)
* The value of cut $(L,C,R)$ is $|C|$.
PARAMETERS:
* $\kappa$:=value of min vertex cut
* $n:=|V|,$ $m:=|E|$
RUNTIME:
* Until recently: near-linear for small $\kappa$. $O(mn)$ for big $\kappa$.
* With isolating cut + almost linear maxflow + tricks:
* almost-linear $(1+\epsilon)$-approximation algorithm that works even for the the weighted case where vertices have weights
* almost-linear exact algorithm (unweighted case only; the weighted case is still open).
* (We will focus on unweighted case here)
**Algorithm sketch:**
1. $(L^*, C^*, R^*)$:= optimal solution. Assume w.l.o.g. $|L^*|\leq |R^*|.$
* **Assume:** $|L^*|\geq |C^*|$.
* We will have to remove this assumption
2. Suppose we know $k:=|L^*|$. (We will guess it as $k=2^i$.)
3. Sample $S\subset V$ where each vertex $v$ is in $S$ w.p. $1/k$.
4. With constant probability $|S\cap L^*|=1$, $|S\cap C^*|=0$, and $|S|\geq 2$.
* This relies on the assumption that $|L^*|\geq |C^*|$.
5. For each $v\in S$, defined a $v$-isolating vertex-cut as a vertex cut $(L,C,R)$ (with respect to $S$) such that $v\in L$ and $(S\setminus \{v\})\subseteq R$.
6. Observe that the minimum $v$-isolating vertex-cut (w.r.t. $S$) among all $v\in S$ is a mininmum vertex-cut.
**Claim:** The isolating cut algorithm where we delete all vertex cuts in Step 1 can be used to compute the min isolating vertex-cuts
**Proof idea:**
* Use submodularity of function $f(X):=|N(X)|$
* Min $(S,T)$ vertex-cut can be found in maxflow time.
![](https://i.imgur.com/sx1RIpU.png)
### Removing assumption $|L^*|\geq |C^*|$
**Approximation algorithm:**
* We can assume that $mindegree(v)> (1+\epsilon)\kappa$.
* If $mindegree(v)\leq (1+\epsilon)\kappa$, then it is a $(1+\epsilon)$-approixmate solution.
* This means that $|L^*|\geq \epsilon |C^*|$. The claim in Step 4 above holds in this case. So, the isolating cut lemma works.
**Exact algorithm:**
* Use isolating cut to deal with the case where $|L^*|\geq |C^*|$ and also the following case:
* Define $C^*_{low}=\{v\in C^*_{low} | deg(v)\leq 8k\}.$
* *Exercise:* We can modify the algorithm above when $|C^*_{low}|<|L^*|polylog(n)$. (Key idea: sample from $V_{low}:==\{v\in V | deg(v)\leq 8k\}.$
* The remaining case is complicated. Roughly, it can be argue that we can construct a small *kernel* that preserve the vertex connectivity by some careful argument using a technique called *sparse recovery sketches.*
## 5. Other applications and limits (sketch)
**Directed cut:** Does not use isolating cut, but use maxflow to find a directed cut that overlaps with a directed tree (arborescence) exactly once.
**Gomory-Hu tree in nearly-quadratic time (FOCS'22):** Use isolating cut and some advanced version of the algorithm for directed cut (on trees) to solve a problem on the tree of some terminal sets.
**Exact weighted vertex cut:** This is an open problem. It is not clear how this problem can benefit from fast maxflow.

See the appendix of the arXiv version (v4) for an updated version adjusted for the directed case. Definitions: Imagine that we order vertices by $s_1, s_2, ..., s_n$. (The order can be arbitrary.) We grow the ball of radius $R_i:=R_{s_i}$ from $s_i$ if $s_i$ is not removed already. ($R_i$ is a random variable.) The only source of randomness in the analysis below is $R_1, R_2, ...$ Let $G_i:=G_i(R_1...R_{i-1})$ be a random variable denoting the graph after we grow balls from $s_1, s_2, \ldots s_{i-1}$.

11/19/2022By Danupon Nanongkai Goal: outline the proof of a theorem about directed Low-Diameter Decomposition (LDD) from [BNW22] (Theorem 1 below). Remarks: These notes have not been subjected to the usual scrutiny reserved for formal publications. The algorithm presented here is slightly different from [BNW22] but the main ideas are the same. Due to this, there might be some errors in these notes. While I tried to make these notes self-contained, the main purpose is to supplement my lecture. I usually start with precise mathematical statements, followed by the discussions. If you are lost in the math, look at the discussions for some help.

9/8/2022Definitions: Imagine that we order vertices by $s_1, s_2, ..., s_n$. (The order can be arbitrary.) We grow the ball of radius $R_i:=R_{s_i}$ from $s_i$ if $s_i$ is not removed already. ($R_i$ is a random variable.) The only source of randomness in the analysis below is $R_1, R_2, ...$ Let $G_i:=G_i(R_1...R_{i-1})$ be a random variable denoting the graph after we grow balls from $s_1, s_2, \ldots s_{i-1}$. $G_i$ is a random variable whose value depends on $R_1,...,R_{i-1}.$

8/31/20221. Detecting a negative-weight cycle Design and analyze a randomized algorithm that, given an input directed weighted graph $G=(V, E)$, in near-linear ($O(|E| (\log |E|)^{O(1)})$) time returns a negative-weight cycle in $G$ if it exists (otherwise, the algorithm returns "no negative cycle"). You can assume that there exists an algorithm $SSSP(G,s)$ that takes as input a graph $G$ and a source $s$ and in near-linear ($O(|E| (\log |E|)^{O(1)})$) time returns the following: If the graph $G$ contains a negative-weight cycle then the algorithm returns "negative cycle" (but it does not report such cycle). If the graph $G$ does not contain a negative-weight cycle then the algorithm returns a shortest path tree $T$ from $s$. Hint:

7/21/2022
Published on ** HackMD**