The Cut-Matching Game: Expanders via Max Flow

알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 알고리즘 연구에서 분할 정복이 가지는 중요성은 어마어마하지만, 그래프에 대한 분할 정복에 대해서는 좋은 결과를 얻지 못했다. 오랜 시간 동안 이러한 분할 정복 은 트리, 평면 그래프, 혹은 이와 유사한 그래프에서만 가능한 것으로 알려져 있었다. 하지만, 그래프 알고리즘과 최적화 이론의 결합이 여러 의미 있는 성과들을 내면서, 이러한 분할 정복 기법을 그래프에서도 적용할 수 있는 좋은 프레임워크가 생겼고, 그 결과 중 하나가 Expander Decomposition이다.

Expander는 잘 연결된 그래프를 뜻한다. 보통 그래프에서 연결성이 크다 라고 하면 Min-Cut의 값이 크다는 식으로 정의한다. 예를 들어, 그래프가 $k$-connected라는 것은 $|E(S, V\setminus S)| \geq k$ 가 모든 $\emptyset \subsetneq S \subsetneq V$ 에 대해 성립한다는 것을 뜻한다. 이 정의에서 유용하고 아름다운 수학적 성질들을 여럿 유도할 수 있지만, 최적 컷 자체의 질을 따진다면 이 정의는 일반적인 경우 $S$ 의 크기가 지나치게 작은 컷을 반환할 가능성이 높다. Expander는 $\frac{|E(S, V \setminus S)|}{min(|S|, |V \setminus S|)} \geq k$ 와 같이, 컷의 크기를 정점 혹은 간선의 개수에 비례하게 나눈 것을 특정 수 이상으로 유지한다. 이 정의는 복잡하여 직접적인 수학적 성질을 얻기 어렵다. 하지만 Expander에서는 여러 알고리즘, 특히 랜덤한 알고리즘들이 굉장히 잘 작동한다는 사실이 잘 알려져 있어 이전부터 알고리즘 뿐만 아니라 암호학(cryptography)에서도 많은 연구가 되어 있는 주제이다. Expander Decomposition은, 그래프의 정점을 이러한 Expander들의 조각으로 파티션하여 문제를 간단하게 만드는 분할 정복 기법이라고 할 수 있다.

Expander Decomposition에 대해서는 이전에 Expander Decomposition and Pruning: Faster, Stronger, and Simpler 라는 글을 통해서 소개한 적이 있다. 이 글은 Expander Decomposition과 Pruning에 걸친 굉장히 넓은 분야를 개괄적으로 조명한 글이다. 모든 내용을 조명할 수 없기에 "무엇을 구하는지" 만 소개하였고 "어떻게 구하는지" 를 소개하지 않았다. 이 글에서는 Expander Decomposition의 핵심 서브루틴인 Cut-Matching Game 에 대해 세부적인 분석을 하는 것을 목표로 한다. 이 서브루틴이 Expander Decomposition의 전부는 아니지만, 핵심 서브루틴인 만큼 Expander Decomposition을 구하는 방법에 대해서 관심이 있다면 좋은 시작점이 될 것이다.

1. Our Task

Expander에서 사용하는 "연결됨" 의 기준은 논문마다 다르다. Application마다 필요한 기준이 달라지는 면이 있기 때문이다. 이 글에서는 다음과 같은 정의를 사용한다.

방향성 없는 연결 그래프 $G = (V, E)$ 에 대해서:

• 어떠한 정점 부분집합 $\emptyset \subsetneq S \subsetneq V$ 에 대해 sparsity $\psi(S) = \frac{|E(S, V \setminus S)|}{min(|S|, |V \setminus S|)}$ 로 정의한다.
• $G$ 의 sparsity 를 $\psi(G) = \min_{\emptyset \subsetneq S \subsetneq V} \psi(S)$ 로 정의한다.
• $\psi(G) \geq \psi$ 면 $G$ 를 $\psi$-expander with regard to sparsity라고 정의하며, 이 글에서는 편의상 $\psi$-expander 라고 부른다.

이번 글의 Main Theorem은 다음과 같다. 아래 알고리즘을 Cut-Matching Algorithm 이라고 부른다.

Theorem 1. 알고리즘 SparsityCertifyOrCut$(G, \psi)$ 는 그래프 $G$ 와 파라미터 $0 < \psi \le 1$ 이 주어졌을 때

• $G$ 가 $\Omega(\psi/\log^2n)$-expander 임을 확인하거나
• $\psi(S)\le O(\psi)$ 인 컷 $S$ 를 반환
  할 수 있다. 이 알고리즘의 시간 복잡도는 $O(\log^2 n) \times T_{max_flow}(G) + \tilde{O}(m)$ 으로, 여기서 $T_{max_flow}(G)$ 는 $G$ 에서 최대 유량을 해결하기 위해 필요한 시간이다.

$T_{max_flow}(G) = O(m^{1 + o(1)})$ 임이 최근 연구에서 밝혀졌기 때문에, 위 알고리즘은 Almost-linear algorithm이다. 사실은, 이 알고리즘에서 Maximum flow를 하는 서브루틴을 Approximate max flow 알고리즘으로 대체할 수 있고, 이를 통해서 위 알고리즘을 Near-linear하게 개선할 수 있다고 알고 있다. 아마 이 논문 에 관련 내용이 있을 것이다. 이 글에서는 여기까지는 소개하지 않는다.

2. Cut-Matching Game: Congestion, and intuition

Cut-Matching Game의 핵심 아이디어를 설명하기 위해, 그래프의 Embedding 이라는 것을 정의할 필요가 있다.

Definition: Embedding. 정점 집합이 동일한 두 그래프 $G, H$ 에 대해서, 함수 $Embed_{H \rightarrow G}$ 는 $H$ 의 간선 $(u, v)$ 를 $G$ 위의 $u - v$ path 에 대응시키는 함수이다. 다시 말해, $P_{u, v} = Embed_{H\rightarrow G}(u, v)$ 이며, $P_{u, v}$ 는 $G$ 위의 $u - v$ path이다.

예를 들어 $G$ 가 트리인 경우에는 $P_{u, v}$ 의 선택이 유일하여, $Embed_{H \rightarrow G}$ 함수가 유일하게 정의된다. 실제로는 트리가 아니기 때문에, $Embed_{H \rightarrow G}$ 함수의 경우가 여러 개 나올 수 있다. Path를 플로우로 생각했을 때, 목표 중 하나는 플로우가 많이 몰린 간선이 없게 하는 것이다. 이를 위해 congestion 개념을 정의한다.

Definition: Congestion. 함수 $Embed_{H \rightarrow G}$ 에 대해 congestion $cong(Embed_{H \rightarrow G}) = max_{e \in E(G)}|{e^\prime \in E(H) | e \in Embed_{H \rightarrow G}(e^\prime)}|$ 이다.

$G, H$ 가 주어졌을 때 $cong(Embed_{H \rightarrow G}) \le c$ 가 가능한지를 판별하는 결정 문제는 Network Flow를 사용하여 almost-linear time에 해결할 수 있다.

이제 다음과 같은 Lemma를 증명한다.
Lemma 2. $\frac{1}{2}$-expander graph $H$ 와 그래프 $G$ 에 대해, $H$ 를 $G$ 에 congestion $C$ 이하로 Embedding할 수 있다면, 즉 $cong(Embed_{H \rightarrow G}) \le C$ 인 함수 $Embed_{H \rightarrow G}$ 가 존재한다면, $G$ 는 $\Omega(\frac{1}{C})$-expander 이다.
Proof. 임의의 컷 $(S, V \setminus S)$ 에 대해 $\frac{|E(S, V \setminus S)|}{min(|S|, |V \setminus S|)} \geq \Omega(\frac{1}{C})$ 를 증명한다. 일반성을 잃지 않고 $|S| \le |V \setminus S|$ 라고 하자. $H$ 가 $\frac{1}{2}$-expander이기 때문에 $E_H(S, V \setminus S) \geq \frac{|S|}{2}$ 를 만족한다. $E_H(S, V\setminus S)$ 에 있는 임의의 간선 $(u, v)$ 는 $Embed_{H \rightarrow G}$ 에서 $(S, V \setminus S)$ 를 한 번 이상 가로지르는 경로에 대응된다. 고로 $(S, V\setminus S)$ 를 가로지르며 경로에 속하는 간선이 $|S|/2$ 개인데, 각 간선은 최대 $C$ 개의 경로를 커버할 수 있다. 고로, $|E_G(S, V \setminus S)| \geq \frac{|S|}{2C}$ 이다. $\blacksquare$

Lemma의 역은 성립하지 않아, Embedding이 없다고 $G$ 에 Low-sparsity cut이 존재하는 것은 아니다.

여기서 Cut-Matching Algorithm의 대략적인 Outline을 설명한다.

• $G$ 에서 확률적인 알고리즘을 사용하여 $\psi(S)\le O(\psi)$ 인 cut (Low-sparsity cut) 을 찾는다.
• 만약 Low-congestion cut이 발견되었다면 Expander가 아니니 그 즉시 종료한다. (Cut Player wins)
• Low-congestion cut이 없다면, 위 확률적 알고리즘의 부산물로 어떠한 크기 $n/2$ 의 매칭을 얻는다. (Matching Player wins)
• 이 과정을 $T = O(\log^2 n)$ 번 반복하면, $T$ 개의 매칭을 얻는다. 이것의 합집합이 $\frac{1}{2}$-expander이며, 이 매칭에 대해 $cong(Embed_{H \rightarrow G}) \le O(\log^2 n / \psi)$ 임을 증명할 수 있다. Lemma 2.1에 의해 그래프가 $\Omega(\psi/\log^2n)$ Expander이다.

3. The Cut-Matching Algorithm

이제 Cut-Matching Algorithm의 아주 구체적인 절차를 설명한다. 알고리즘 SparsityCertifyOrCut$(G, \psi)$ 는 그래프 $G$ 와 파라미터 $0 < \psi \le 1$ 이 주어졌을 때

• Lemma 2.1에 의해 $G$ 가 $\Omega(\psi/\log^2n)$-expander 임을 검증하는, 즉 $cong(Embed_{H \rightarrow G}) \le O(\log^2 n / \psi)$ 가 존재하는 $\frac{1}{2}$-expander $H$ 를 반환하거나
• $\psi(S)\le O(\psi)$ 인 컷 $S$ 를 반환

하는 알고리즘이다. 시간 복잡도는 $O(\log^2 n) \times T_{max_flow}(G) + \tilde{O}(m)$ 이다.

알고리즘은, $i = 0, 1, \ldots, \Omega(\log^2 n)$ 번에 걸쳐:

• $(S_i, \overline{S_i}) =$ FindBipartition$(G, {M_1, M_2, \ldots, M_i})$. 이 때 $|S_i| = |\overline{S_i}| = n/2$ 임이 보장된다.
• $G$ 의 모든 간선 $e$ 의 용량을 $\frac{1}{\psi}$ 로 두고, 모든 $v \in S_i$ 에 대해 Source 에서 $1$ 의 용량, $v \notin S_i$ 에 대해 Sink로 $1$ 의 용량이 있는 Network flow 문제를 해결한다. WLOG $\frac{1}{\psi}$ 는 정수라고 가정한다.
• 만약 위 플로우 문제가 $n/2$ 크기의 플로우를 찾는다면, $G$ 의 Flow decomposition을 찾는다. Flow decomposition에 따라 $v \in S$ 로 유입된 플로우가 $w \notin S$ 로 매칭될 것인데, 이 $n/2$ 개의 쌍 $(v, w)$ 를 매칭 $M_{i+1}$ 로 둔다.
• 만약 그렇지 못한다면, Minimum cut을 반환한다.

이후 $H = \bigcup_i M_i$ 를 반환한다.

FindBipartition 이라는 함수가 어떤 함수인지에 대해서는 이후에 설명한다.

이 알고리즘을 증명하기 위해서는

• 알고리즘이 $H$ 를 반환했을 때 이것이 조건을 만족하는지
• 알고리즘이 $S$ 를 반환했을 때 이것이 조건을 만족하는지
• 주어진 시간 복잡도에 종료하는지

를 증명해야 한다. 일단은 FindBipartition 함수에 대한 정보를 알아야 앞선 3개의 질문에 대해 제대로 된 대답을 할 것이니, 이에 대한 증명도 이 챕터에서는 하지 않는다. 그러나, 이와 별개로 두 번째 질문, 즉 위 알고리즘이 반환한 Minimum cut이 $\psi(S) \le O(\psi)$ 를 만족하는 건 지금도 증명할 수 있다.

Lemma 3.1. 알고리즘이 최소 컷 $(X, V \setminus X)$ 를 반환했다면, $\psi(X) = O(\psi)$ 를 만족한다.
Proof. 임의의 컷은 세 종류의 간선들로 구성되는데, Source에서 $S_i$ 로 가는 간선 중 끊긴 것, $\overline{S_i}$ 에서 Sink로 가는 간선 중 끊긴 것, 그리고 그 사이에 끊긴 것들이다. 첫 번째 종류의 간선의 $G$ 상 끝점 집합을 $N_S = (V \setminus X) \cap S_i$, 두 번째 종류의 간선의 $G$ 상 끝점 집합을 $N_T = X\cap \overline{S_i}$ 라고 하자. 그 사이에 끊겨야 하는 간선들은, $(X, V\setminus X)$ 를 기준으로 양 끝점이 컷의 다른 쪽에 속하는 간선들이다. 고로, 끊은 간선들의 가중치 합을 생각해 보면

$\frac{1}{\psi}|E(X, V\setminus X)| + |N_S| + |N_T| < n/2$
$|E(X, V\setminus X)| < \psi(n/2 - |N_S| - |N_T|)$
$\frac{|E(X, V \setminus X)|}{\min(|X|, |V \setminus X|)} < \frac{\psi(n/2-|N_S|-|N_T|)}{\min(|X|, |V \setminus X|)}$

그런데, $|X| \geq n / 2 - |N_S|, |V \setminus X| \geq n / 2 - |N_T|$ 이기 때문에
$\min(|X|, |V \setminus X|) \geq \min(n / 2- |N_S|, n / 2 - |N_T|) \geq n / 2 - |N_S| - |N_T|$

고로 $\psi(X) < \psi$ 이다. $\blacksquare$

4. Implementation of FindBipartition by Random Walks

FindBipartition 함수는 그래프와 함께 $T+1$ 개의 완벽 매칭 ${M_1, M_2, \ldots, M_{T+1}}$ 을 입력으로 받는다. 이 매칭에 대해 random walk를 하는 것이 알고리즘의 중요한 요소이다. random walk의 $i$ 번째 단계에서는, 현재 위치에서 매칭 $M_i$ 의 반대쪽 정점으로 $1/2$ 의 확률로 움직이고, $1/2$ 의 확률로 가만히 있는다. $p^t_{i \rightarrow j}$ 를, $i$ 에서 시작하여 $t$ 번의 random walk 이후 $j$ 로 도착할 확률이라고 하고, $p_i^t = [p_{1 \rightarrow i}^t, p_{2 \rightarrow i}^t, \ldots, p_{n \rightarrow i}^t]^T$ 라고 하자. $(i, j) \in M_{t + 1}$ 이라고 할 때 $p_i^{t + 1}=p_j^{t + 1} = \frac{1}{2}(p_i^t + p_j^t)$ 이 성립한다. (여담으로, 이렇게 절반의 확률로 가만히 있거나 절반의 확률로 다른 정점으로 이동하는 형태의 Random walk를 Lazy random walk 라고 부르며 이 문제 외에도 다양한 응용이 있다.)

$p_i^t$ 를 column vector로 가지는 행렬을 $\Pi^t$ 라고 하자. 수학적 귀납법을 통해, $\Pi_t$ 의 모든 행의 합은 1이고, 모든 열의 합도 1임을 보일 수 있다 (직관적으로도 자명). 이러한 행렬을 어려운 말로 doubly-stochastic 하다고 한다.

만약에 어떠한 random walk가 모든 $i, j$ 에 대해 $p_{j \rightarrow i}^t \geq \frac{1}{2n}$ 을 만족한다면, 이 random walk가 mixing at step $t$ 라고 한다. 이 사실은 매칭의 합집합이 Expander라는 사실과 밀접한 연관이 있다.

Lemma 4.1. 만약 어떤 매칭 ${M_1, M_2, \ldots, M_t}$ 에 대한 random walk가 step $t$ 에서 mixing한다면, $H = \bigcup_{i \leq t} M_i$ 는 $\frac{1}{2}$-expander 이다.
Proof. $|S| \leq |V \setminus S|$ 를 만족하는 임의의 컷 $S$ 를 잡자. 확률 $p_{i \rightarrow j}$ 를 해석할 때 어떠한 질량 이 움직인다 라는 비유를 사용하면 편하다. 이렇게 볼 경우, mixing한다는 것은 임의의 $i$ 에서 $j$ 로 $\frac{1}{2n}$ 의 질량이 이동해야 한다는 것을 의미한다. $|V \setminus S| \geq \frac{n}{2}$ 이기 때문에, Random walk 전체를 두고 보면 $|S| \times \frac{n}{2} \times \frac{1}{2n} = \frac{|S|}{4}$ 이상의 질량이 $|S|$ 에서 $|V \setminus S|$ 로 이동했다. 매칭의 각 간선은 매 iteration마다 최대 $\frac{1}{2}$ 의 질량을 옮길 수 있고, 그러기 위해서는 해당 간선이 컷을 가로질러야 한다. 고로 $H$ 에는 $S$ 를 가로지르는 간선이 최소 $\frac{|S|}{2}$ 개 있으며, 고로 임의의 컷에 대한 sparsity가 $\frac{1}{2}$ 이상임이 증명된다. $\blacksquare$

이제 FindBipartition 알고리즘을 소개한다.

• $\sum_{i \in [n]} r_i = 0$ 인 $n$ 차원 벡터 $r$ 을 랜덤하게 고른다.
• $u = \Pi^t \cdot r$ 을 계산한다.
• ${1, 2, \ldots, n}$ 을 $u_i$ 값의 크기 증가 순으로 정렬하고, 앞의 $n/2$ 개 원소를 $S$, 남는 원소를 $\overline{S}$ 로 둔다.
• $(S, \overline{S})$ 를 반환한다.

알고리즘이 꽤 간단한 편이다. 잠깐 Main Algorithm으로 돌아가서, 시간 복잡도를 분석하자.

Theorem 3.2. SparsityCertifyOrCut$(G, \psi)$ 는 $O(\log^2 n) \times T_{max_flow}(G) + \tilde{O}(m)$ 에 동작한다.
Proof. 먼저 FindBipartition 알고리즘이 $O(n \log^2 n)$ 에 동작함을 관찰할 수 있다. 행렬 전체는 Dense할 수 있으나, $\Pi^t \cdot r$ 에서 $\Pi^{t + 1} \cdot r$ 로 $O(n)$ 시간에 전이할 수 있기 때문이다. 그 외 모든 연산은 $O(n)$ 에 동작한다. 또한, Flow decomposition은 Link-cut tree를 사용하여 $\tilde{O}(m)$ 시간에 찾을 수 있음이 알려져 있다. 고로, Flow는 $O(\log^2 n)$ 번 호출하고, 그 외 연산이 $O(n \log^4 n) + \tilde{O}(m) =\tilde{O}(m)$ 이다. $\blacksquare$
Remark. 사실 Flow decomposition이 왜 $\tilde{O}(m)$ 에 찾아지는지 정확히 안 알아봤다. 아마 General case에서는 안 되고, 이 경우에는 전체 플로우가 $n/2$ 라서 가능한 것 같다. 일단 해당 내용은 저자의 Homework 를 믿고 사용하였다.

고로 세 질문 중 두 질문을 대답했다. 마지막 남은 질문이 가장 어렵다고 할 수 있다. 일단 앞의 내용을 잠시 상기하자: 만약 모든 $(i, j)$ 에 대해 $p_{j \rightarrow i}^t \geq \frac{1}{2n}$ 를 만족한다면 $H = \cup M_i$ 는 Expander이다. 즉, $p_{j}^t$ 가 균일 하면 Expander가 된다는 뜻이다. 여기서 출발하면 step $t$ 에 대한 퍼텐셜 함수를 아래와 같이 정의할 수 있다.

$\Phi^t = \sum_{i, j} (p_{i \rightarrow j}^t - 1/n)^2 = \sum_i ||p_t - \textbf{1}/n||_2^2$

Claim 4.2. SparsityCertifyOrCut 알고리즘의 반복 과정에서 $E[\Phi^t - \Phi^{t+1}] = \Omega(\Phi^t / \log n) - O(n^{-5})$ 를 만족한다. 또한, $\Phi^t - \Phi^{t+1} \geq 0$ 이 항상 만족된다. 기댓값은 현재 라운드의 모든 랜덤 벡터 $\textbf{r}$ 에 대해 취해진다.

Corollary 4.3. $T = \Theta(\log^2 n)$ 일 때 SparsityCertifyOrCut 알고리즘의 반복 과정에서 $\Phi^{T+1} \le \frac{1}{4n^2}$ 이다.
Proof of Corollary 4.3. 기본적으로, 매 단계에서 $O(1/\log n)$ 비율의 퍼텐셜이 빠진다. 고로 퍼텐셜을 반으로 줄이려면 $O(\log n)$ 회의 iteration이 필요하고, $1/n$ 으로 줄이려면 $O(\log^2 n)$ 회의 iteration이 필요하다. 초기 퍼텐셜이 최대 $O(n)$ 이니까, 기댓값으로 정직하게 감소한다고 하면 $O(\log^2 n)$ 회의 반복이 맞다. $X^i$ 를 $i$ 번째 iteration에서 퍼텐셜이 $\Omega(1/\log n)$ 배 이상 빠졌을 때 1, 아니면 0인 확률 변수라고 정의하면, Chernoff bound를 사용하여 높은 확률로 $O(\log^2 n)$ 회의 반복이 충분함을 보일 수 있다. $O(n^{-5})$ 은 작아서 처음부터 무시해도 된다. $\blacksquare$

Corollary 4.4. SparsityCertifyOrCut 알고리즘이 반환하는 $H$ 는 $cong(Embed_{H \rightarrow G}) \le O(\log^2 n / \psi)$ 가 존재하는 $\frac{1}{2}$-expander 이다.
Proof of Corollary 4.4. 알고리즘에 의해 $M_i$ 에 대해서 Flow 문제에 해가 있었기 때문에 $cong(Embed_{M_i \rightarrow G}) \le 1/\psi$ 이고, 고로 $cong(Embed_{H \rightarrow G}) \le O(\log^2 n /\psi)$ 도 자동적으로 성립한다. $H$ 가 $\frac{1}{2}$-expander 가 아니라면, $\Pi^t$ 는 mixing하지 않고, 고로 $(p_{i, j} - 1 / n)^2 > \frac{1}{4n^2}$ 인 $(i, j)$ 가 존재하는데, 이는 Corollary 4.3에 모순이다. $\blacksquare$

Claim 4.2가 참이라면, Corollary 4.4에 의해 알고리즘 전체가 증명된다.

Proof of Claim 4.2

먼저 퍼텐셜의 감소량을 한번 써 보자. $M_{t + 1}$ 이 Perfect matching이고, $p_i^{t + 1}=p_j^{t + 1} = \frac{1}{2}(p_i^t + p_j^t)$ 임을 사용한다. (따로 적혀있지 않으면 $L_2$ norm이다. 수식이 깨진다. ㅠㅠ)

$\Phi^t - \Phi^{t+1}$
$= \sum_i ||p_i^t - \textbf{1}/n||^2 - \sum_i ||p_i^{t+1} - \textbf{1}/n||^2$
$= \sum_i ||p_i^t - \textbf{1}/n||^2 - \sum_{(i, j) \in M_{t+1}} 2||\frac{p_i^t+p_j^t}{2} - \textbf{1}/n||^2$
$=\sum_{(i, j) \in M_{t+1}} ||p_i^t - \textbf{1}/n||^2 +||p_j^t - \textbf{1}/n||^2 -2||\frac{p_i^t+p_j^t}{2} - \textbf{1}/n||^2$

$||x||^2 + ||y||^2 - 2||(x+y)/2||^2 = \frac{1}{2}||x-y||^2$ 임을 사용하면

$\Phi^t - \Phi^{t+1} = \frac{1}{2} \sum_{(i, j) \in M_{t+1}} ||p_i^t - p_j^t||_2^2$

라는 아주 깔끔한 식으로 정리된다.

여기서 관찰해야 할 것은, $p_i^t$ 와 $p_j^t$ 의 차이가 클 수록 퍼텐셜을 더 줄일 수 있다는 것이다. 고로 매칭을 구할 때 거리가 먼 벡터끼리 매칭을 해 주는 것이 좋을 것이다. 나이브한 생각은 Max cost perfect matching을 찾는 것이지만 시간 복잡도 상으로도 느리고 bound 상으로도 좋은 정보를 얻어가기 어렵다. 여기서의 아이디어는 랜덤 벡터 $r$ 를 잡고, $r \cdot p_i^t$ 가 작은 것과 큰 것 사이의 arbitrary matching을 찾는 것이다. 수직선 상에 projection하면 잡을 수 있는 매칭이 자유롭기 때문에, 여기에 Flow를 섞어서 congestion 부분 역시 해결할 수 있었다.

$u(i) = p_i^t \cdot r$ 이라고 했을 때, whp ($\geq 1 - n^{-7}$) 로 다음 사실이 성립한다:
$\Phi^t - \Phi^{t+1} = \frac{1}{2} \sum_{(i, j) \in M_{t+1}} ||p_i^t - p_j^t||^2 \geq \frac{n-1}{64 \log n} \sum_{(i, j) \in M_{t+1}}|u(i) - u(j)|^2$

이를 증명하기 위해서는, 임의의 $(i,j) \in V$ 에 대해 $||p_i^t - p_j^t|| \geq \frac{n-1}{64\log n}|u(i) - u(j)|^2$ 일 확률이 $\geq 1-n^{-8}$ 이상임을 보이면 된다. Union bound가 성립하기 때문이다. 이 사실의 증명을 위해 다음 Theorem을 빌려 쓴다. (이 Theorem은 증명하지 않는다.)

Theorem 4.5. $y \in \mathbb{R}^d$ 가 길이 $l$ 의 벡터고, $r \in \mathbb{R}^d$ 가 random unit vector라면, 다음이 성립한다:

• $E[(y \cdot r)]^2 = \frac{l^2}{d}$
• $x \leq d/16$ 에 대해 $P[(y \cdot r)^2 \geq \frac{xl^2}{d}] \leq e^{-x/4}$

여기에 $d = n - 1$, $l = 1$, $x = 32\log n$ 을 대입하면 다음이 성립한다 ($d = n - 1$인 이유는, $(p_i^t - p_j^t)$ 와 $r$ 이 모두 $\textbf{1}$ 과 orthogonal하기 때문이다.)

$P[((p_i^t - p_j^t) \cdot r)^2 \geq \frac{32 \log n}{n - 1}||p_i^t - p_j^t||_2^2] \leq e^{-8\log n} = n^{-8}$
$P[\frac{n-1}{64 \log n} (u_i - u_j)^2 \geq \frac{1}{2} ||p_i^t - p_j^t||_2^2] \leq e^{-8\log n} = n^{-8}$

$\mu = \max_{i \in S} u(i)$ 라고 하면, $u(i) \le \mu$ 가 모든 $i \in S$ 에 대해 성립하고, $\mu \leq u(j)$ 가 모든 $j \notin S$ 에 대해 성립한다. 식을 정리하면
$\Phi^t - \Phi^{t+1} \geq \frac{n - 1}{64\log n} \sum_{(i, j) \in M_{t+1}}|u(i) - u(j)|^2$
$\geq \frac{n - 1}{64\log n} \sum_{(i, j) \in M_{t+1}}(u(i) - \mu)^2 + (u(j) - \mu)^2$
$= \frac{n - 1}{64\log n} \sum_{i}(u(i) - \mu)^2$
$= \frac{n - 1}{64\log n} \sum_{i} u(i)^2 - 2\mu \sum_i u(i) + n\mu^2$
$\geq \frac{n - 1}{64\log n} \sum_{i} u(i)^2$
이다. 마지막 전개는, $r$ 의 정의와 $\Pi^t$ 의 doubly-stochastic함에 의해 $\sum_i u(i) = (\sum_{i} p_i^t) \cdot r = \textbf{1} \cdot r = 0$ 이라는 점에서 유도된다.

마지막으로, Theorem 4.5의 첫번째 명제를 다시 적용해서 ($r \cdot \textbf{1} = 0$ 임도 사용)
$E[\sum_i u(i)^2] = \sum_i E[u(i)^2] = \sum_i E[(p_i^t \cdot r)^2] \geq \sum_i E[(p_i^t - \textbf{1}/n) \cdot r)^2] = \sum_i \frac{||p_i^t - \textbf{1}/n||_2^2}{n-1} = \frac{\Phi^t}{n-1}$

이러면 끝난 것 같지만, 사실 이건 $1 - n^{-7}$ 이상의 확률이 성립할 때만 가능한 주장이다. 그렇지 않은 경우를 고려해 주기 위해 $p_i^t, r$ 이 모두 unit vector고, 따라서 $\sum u(i)^2 \le n$ 임을 이용해야 한다. 이에 따라 $n^{-6}$ 의 Error term이 붙는다. 모두 정리하면

$E[\Phi^t - \Phi^{t+1}]\geq \frac{n - 1}{64\log n}(\frac{\Phi^t}{n - 1}-n^{-6}) = \Omega(\Phi^t/\log n) - O(n^{-5})$

가 성립한다.

5. Remarks

이 알고리즘이 컷을 반환할 때는 항상 올바른 Low-sparsity cut을 반환함이 보장된다. 하지만 Expander를 반환할 때는 $T$가 만약에 충분히 작지 않으면 $\frac{1}{2}$-expander가 아닌, 조금 불량한 expander가 나올 수도 있다. 즉, $T$ 가 고정되었을 경우 이 알고리즘은 Monte-Carlo algorithm이다. 공학적으로는 $T$ 를 어느 정도로 줘야 Cut을 항상 찾는지, 중간에 expander임이 확실시 되면 일찍 끊어줄 수 있는지, 등등을 실험해 볼 여지가 있다.

위 Cut-Matching Algorithm에 기반한 Expander decomposition의 구현을 시도한 프로젝트가 있다. 코드가 3500줄에 달하지만, Competitive programming 식으로 짜인 코드가 아니기 때문에 로직 자체는 간단할 수도 있어 보인다. 관심이 있다면 이 링크 를 참고하면 좋을 것 같다.