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