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


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


**Step 2: Work on each component $U_v$ separately.**
* $𝐺_𝑣$ := contract $𝑉\setminus 𝑈_𝑣$ into sink $𝑡_𝑣$.
* Compute $(v,t_v)$ mincut.


---

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


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


---

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


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


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