Approximation of MAX CUT

오늘 다룰 Max Cut 문제는 non-negative weighted undirected graph $G = (V, E, w)$에 대해서 $S \subseteq V$를 골라서 $vE(S, V - S)$의 weight 합을 최대화하는 문제이다. 다항 시간 알고리즘이 알려진 min cut에 비해 이 문제는 NP-hard임이 알려져 있다.

NP-hard problem의 경우 여러 근사 알고리즘들이 존재하는데, 가장 naive한 알고리즘부터 생각해보자. 임의의 $S \subseteq V$에 대해 $E(S, V-S)$의 weight 합, 즉 $\sum_{e \in E(S, V-S)} w(e)$를 $w(\partial S)$라고 표기하자. $w(\partial S)$의 가능한 최댓값, 즉 MAX CUT을 $\mathrm{OPT} = w(\partial S^{OPT})$라고 표기한다.

각 정점에 $1/2$의 확률로 0, 1을 라벨링하고, 0으로 라벨링 된 정점을 $S$로 선택한다. 이 경우 각 간선이 cut에 포함될 확률은 $1/2$이기 때문에 $\mathbb{E}[w(\partial S)] = \sum_{e} w(e)/2 \ge \mathrm{OPT}/2$가 된다. 즉 이 알고리즘은 Max Cut 문제의 (randomized) $1/2$-approximation algorithm이 된다.

Goemans-Williamson Algorithm

Approximation algorithm을 찾을 때 많이 사용하는 전략 중 하나가 문제를 Integer Linear Program으로 표현하는 것이다. 각 정점 $i$에 대해 변수 $x_{i}$를 정의하자.

$$\begin{aligned} \mathrm{maximize} & \sum_{i, j \in E} \frac{w _ {i,j}}{2}(1 - x_{i}x_{j}) \\ \mathrm{s.t.} & x_{i} \in \lbrace -1, 1 \rbrace \end{aligned}$$

$x_{i} = -1$인 정점 $i$의 모임을 $S$로 생각하면 이 문제가 max cut을 모델링한다는 것을 확인할 수 있다.
가장 편하게 할 수 있는 생각은 $x _ {i} \in [-1, 1]$이도록 relaxation해주는 것인데, 두 가지 문제가 있다.

• LP와 다르게 objective function이 $x$에 대해 non-linear하다. 이를 다항 시간 안에 해결할 수 있는가?
• 어떤 최적해 $x^{\ast}$가 주어졌을 때, 이를 어떻게 $\hat{x} \in {-1, 1}^{n}$으로 rounding할 수 있겠는가?

단순한 relaxation으로는 두 가지 모두에 대해 긍정적인 답을 하기 어렵다. Goemans-Williamson algorithm은 이 문제를 Semidefinite programming으로 접근한다. 각 정점의 라벨에 해당하는 변수 $x _ {i}$를 실수 하나가 아닌 $n$차원 unit vector $v _ {i}$에 대응시키자. $n$은 정점 개수와 정확히 같다. 다시 모델링 된 문제는 다음과 같다.

$$\begin{aligned} \mathrm{maximize} & \sum_{i, j \in E} \frac{w _ {i,j}}{2}(1 - v_{i} \cdot v_{j}) \\ \mathrm{s.t.} & v_{i} \cdot v_{i} = 1 \end{aligned}$$

우선 문제 전체가 SDP의 형태를 띠고 있기 때문에 항상 다항 시간 해결법이 존재한다. (각 벡터가 $n$차원이어야 SDP의 조건을 만족한다) 또한 임의의 max cut $S^{OPT}$의 경우 $i \in S^{OPT}$일 때 $i = \mathbf{e} _ {1}$, 그렇지 않으면 $i = -\mathbf{e} _ {1}$으로 두 antipodal한 벡터로 정점들을 갈라놓으면 이는 항상 feasible SDP solution이 되므로, 위 SDP는 max cut의 실제 relaxation이기도 하다.

그렇다면 두 번째 질문인, SDP solution을 어떻게 max cut으로 바꿀 것이냐는 rounding 문제를 해결해야 한다. 가장 단순하게는 아무 "적도"를 잡아서, 북반구를 $+1$, 남반구를 $-1$에 대응시키면 될 것 같다. 이를 좀 더 엄밀하게 표현하면, 어떤 unit vector $p$을 잡아 $v_{i} \cdot p \ge 0$인 $i$들을 $S$ 로 설정한다는 뜻이다.

그런 $p$를 어떻게 찾는지는 별로 안 궁금하니, 일단 그런 $p$를 잘 잡을 수 있다고 생각하자. 즉, $n$차원 sphere위에서 uniformly random하게 뽑은 한 벡터 $p$를 어떻게 잘 가지고 왔다고 하자. 이제 이로 인해 생기는 cut의 value와 optimum LP value 사이의 관계식이 필요하다.

상식적으로 두 벡터 $v _ {i}, v _ {j}$가 antipodal하다면 간선 $ij$는 무조건 cut에 포함될 것이고, 같은 방향이라면 절대 cut에 포함되지 않을 것이다. 만약 두 벡터가 이루는 각이 $0 < \theta _ {ij} < \pi$ 라면 어떨까? 구를 그려놓고 $v _ {i}$를 북반구에 포함시킬 $p$의 범위같은 걸 그려보면, 둘이 다른 반구에 속할 확률이 $\frac{\theta _ {ij}}{\pi}$ 가 됨을 알 수 있다.

즉, $\mathbb{E} _ {p} [ w(\partial S) ] = \sum_{i, j \in E} w _ {ij}\frac{\theta _ {ij} }{\pi}$가 된다.
한편 LP optimum의 경우 $\sum_{i, j \in E} w _ {ij} \frac{1}{2}(1 - v_{i} \cdot v_{j}) = \sum_{i, j \in E} w _ {ij} \frac{1}{2}(1 - \cos \theta _ {ij})$가 될 테니, $\min_{0 \le t \le \pi} \frac{t/\pi}{1/2(1 - \cos t)}$가 approximation ratio가 될 것이다. 이는 $t \approx 2.33$에서 약 $0.878$이 나온다. 즉, max cut에 대한 $0.878$-approximation algorithm을 얻은 것이다.

위에선 생략했지만, unit sphere 위에서 $p$를 uniform random sampling하는 것은 생각보다 간단하다. $p$의 각 coordinate을 $\mathcal{N}(0,1)$에서 뽑고, 이를 normalize해주면 된다.

Inapproximability of MAX CUT under Unique Games Conjecture

Unique Games Conjecture는 주변인에게서 여러 번 들었지만 아직도 공부가 부족하다. 이게 왜 Game인지도 모르겠고, 이게 어렵다고 생각하게 된 동기도 아직 잘 모르겠다. 실제로 Subhash Khot이 2002년 경 제안한 개념으로 그렇게 오래된 문제는 아니지만, inapproximability에 관한 여러 bound를 혁신적으로 줄여서 주목받은 것으로 알고 있다.

Definition (Bipartite Unique Games)

• 그래프 $G = (U \cap V, E)$가 주어진다.
• 또한, "alphabet size" $k$가 주어진다.

우리의 임무는, 각 정점에 $1$에서 $k$의 수를 labeling하는 것이다. 이 때 제약 조건이 아래와 같이 주어진다.

• 각 간선 $e = uv$마다 "required permutation" $\pi _ {e} \in S_{k}$가 존재한다. $i, j \in [k]$에 대해 $\pi_{e} (i) = j$라는 것은, $u$의 label이 $i$라면 $v$의 label이 $j$여야 한다는 것을 의미한다. 이 조건이 만족된다면 간선 $e$는 "satisfied"되었다고 한다.

벌써부터 문제가 어려운데, conjecture의 내용은 더 아리송하다.

Definition. (Unique Games Conjecture)

GAP-$(\varepsilon, 1 - \varepsilon)$ unique games 문제의 경우, 출제자가 다음을 보장해준다.

• 적어도 전체의 $1 - \varepsilon$ 이상의 간선이 satisfy되는 labeling이 존재한다.
• 또는, 어떤 labeling도 전체의 $\varepsilon$ 이상을 satisfy시킬 수 없다.

우리의 임무는 주어진 instance가 어느 쪽에 속하는지 알아내는 것이다.

Unique Games Conjecture란, 모든 $\varepsilon > 0$에 대해 GAP-$(\varepsilon, 1 - \varepsilon)$-unique games가 np-hard가 되는 어떤 상수 $k$가 존재한다는 것을 의미한다. $k$가 상수라는 것은, 앞으로 복잡도에 있어 $k$는 고려하지 않는다는 것이다.

어쨌든, 우리는 이 unique games 문제를 max-cut으로 reduction하여 approximation hardness를 보일 것이다. 이를 GAP-preserving reduction이라고도 부른다.

Claim. 모든 $\varepsilon^{\prime} > 0$, $\rho \in (-1, 0]$에 대해, GAP-$(\varepsilon, 1 - \varepsilon)$-UG를 GAP-$(\frac{\cos^{-1} \rho}{\pi} + \varepsilon^{\prime}, (1 - 2\varepsilon)\frac{1 - \rho}{2})$-MAX CUT을 이용하여 해결할 수 있도록 하는 $\varepsilon > 0$이 존재한다.

GAP-$(\alpha, \beta)$ max cut이란, 편의상 간선의 weight 합이 $1$이라고 가정했을 때

• value가 $\alpha$ 이상인 cut이 존재하거나
• value가 $\beta$ 이상인 cut이 존재하지 않음
  을 보장해주는 문제이다. 만약 Claim이 사실이라면, max cut의 approximation ratio는 $\left(\frac{\cos^{-1} \rho}{\pi} + \varepsilon^{\prime}\right) / (1 - 2\varepsilon)\frac{1 - \rho}{2}$ 를 넘을 수 없다. approximation solution의 value만 보고 GAP 문제를 바로 해결할 수 있기 때문이다. $\rho \in (-1, 0]$에 대해 식을 최소화하면 $\frac{0.878 + \varepsilon^{\prime}}{1 - 2\varepsilon}$를 얻는데, $\varepsilon^{\prime}$을 조정하면 임의의 $\varepsilon^{\prime} > 0$에 대해 $0.878 + \varepsilon^{\prime}$ approximation hardness를 보인 셈이다.

이제 UG instance, 즉 bipartite graph $G = (U \cup V, E)$와 순열들 $\pi_{e}$가 주어졌을 때 max cut instance $G^{\prime}$로 만들자. 원하는 바를 다시금 정리하면

• (Completeness) 전체의 $1 - \varepsilon$이상을 만족시키는 labeling $l$이 존재하면, $G^{\prime}$에는 $(1 - 2\varepsilon)\frac{1 - \rho}{2}$ 이상의 value를 갖는 cut이 존재한다.
• (Soundness) 만약 모든 labeling이 전체의 $\varepsilon$밖에 만족시키지 못한다면, $G^{\prime}$에는 value가 $\frac{\cos^{-1} \rho}{\pi} + \varepsilon^{\prime}$ 이상인 cut이 존재하지 않는다. 뒤집어 말해, $G^{\prime}$에 value가 그보다 높은 cut이 존재한다면 $\varepsilon$ 이상을 만족시키는 labeling $l$이 존재해야 한다.

Reduction은 굉장히 비직관적으로 만든다. $G'$의 정점은 $V \times 2^{[k]}$가 될 것인데, 즉 $v \in V, S \subseteq [k]$마다 정점 $(v, S)$가 생길 것이다. $V$는 UG instance에서 bipartite graph의 한 쪽 정점임에 주목하자.

 

이 때 $(v, S), (w, T)$마다 간선을 이어줄 건데, 이 간선의 weight는 아래의 시행으로 인해 이 간선이 출력될 확률로 정의한다. weight가 확률이니, 모든 간선의 weight를 더하면 $1$이 나올 것은 자명하다.

 

시행:

1. $u \in U$를 uniform하게 고른다.

2. $v, w \in \mathcal{N}(u)$를 uniformly random, independent하게 고른다. (두 정점이 다를 필요는 없다)

3. $S_{1} \subseteq [k]$를 uniformly random하게 고른다.

4. $T_{1} \subseteq [k]$를 고르되, 각 $i \in [k]$에 대해 $\Pr[(i \in S_{1}) = (i \in T_{1})] = \frac{1 + \rho}{2}$가 성립하도록 한다.

5. $e = uv \in E(G)$에 대해, $S = \pi_{e}(S_{1})$, 마찬가지로 $T = \pi_{uw}(T_{1})$으로 바꾼다. 즉, $X = \pi(X_{1})$이란 오른쪽을 $X_{1}$ 중 하나로 고르고 싶을 때 왼쪽에 가능한 label의 목록이다.

output: $(v, S)$와 $(w, T)$ 사이의 간선.

 

어차피 cut의 weight만 볼 거기 때문에 각 간선의 weight를 정확하게 계산하는 건 머리만 아프지 별로 필요 없다.

 

Completeness Proof

이제 어떤 labeling $l : U \cup V$가 존재해서, 전체의 $1 - \varepsilon$에 해당하는 간선 $e=uv$에 대해 $\pi_{e}(l(u)) = l(v)$가 성립한다고 하자. 이제 위의 시행을 거쳐서 만든 간선이 cut에 있을 확률을 계산하자.

 

각 정점 $(v, S)$에 대해, $l(v) \in S$인 정점들을 cut으로 보고, 시행을 반복하자.

 

1번과 2번 과정에서, $uv$와 $uw$가 unsatisfied vertex일 확률이 각각 $\varepsilon$ 이하이니 최소한 $1 - 2\varepsilon$ 이상의 확률로 $l(u) = \pi(l(v)) = \pi(l(w))$가 성립한다. ($\pi$의 아래첨자는 의미상 명확한 경우 생략한다)

 

3번과 4번 과정에서, $l(u)$가 한쪽에만 들어있는 $S, T$를 고르게 될 확률이 $\frac{1 - \rho}{2}$가 된다.

따라서 5번 과정을 통해 변환하고 나면, $l(v) \in S$, $l(w) \in T$ 중 하나만 성립할 확률도 똑같이 $\frac{1 - \rho}{2}$이다.

 

따라서, 시행에서 cut에 들어있는 간선을 뽑을 확률은 최소한 $(1 - 2\varepsilon)\frac{1 - \rho}{2}$ 이상이 된다.

 

Soundness Proof

이해하는 데 가장 시간을 많이 쓴 부분이고, 사실 아직 완전히 이해하지도 못했다. discrete fourier analysis라는 키워드가 많이 등장하는데 아직 잘 모르겠다.

 

목표는 $\frac{\cos^{-1} \rho}{\pi} + \varepsilon^{\prime}$ 이상의 max cut assignment를 $\varepsilon$ 이상의 satisfying label을 주는 적절한 $\varepsilon$ 값을 찾는 것이다.

 

$f_{v}(S) : 2^{[k]} \to \{-1, 1\}$를 정점 $(v, S)$의 max cut labeling이라고 하자. Integer LP와 비슷하게, 이 때 cut value는

$$\mathrm{val} = \frac{1}{2}\mathbb{E}_{u, v, w, S, T} \left[ 1 - f_{v}(\pi(S))f_{w}(\pi(T)) \right]$$

가 될 것이다. 기댓값 연산자는 시행의 distribution에 따른 것으로, 독립인 부분을 묶어내기 위해 $h_{u}(S) = \mathbb{E}_{v \in N(u)} f_{v}(\pi(S))$로 정의하자. $h_{u} : 2^{[k]} \to [-1, 1]$임을 알 수 있다.

 

$$\mathrm{val} = \frac{1}{2}\left(1 - \mathbb{E}_{S, T} [h_{u}(S)h_{u}(T)]\right)$$

로 정리된다. 이 때 $\mathcal{S}_{\rho}(h_{u}) := \mathbb{E}_{S, T} [h_{u}(S)h_{u}(T)]$를 $h_{u}$의 stability로 정의한다. 어떤 $S$에 대해 $\frac{1 - \rho}{2}$의 확률로 원소를 변조했을 때 자신과의 correlation이 얼마나 유지되는지를 나타낸 값으로 생각할 수 있다.

 

즉 $\mathrm{val} = \frac{1}{2}(1 - \mathbb{E}_{u} [ \mathcal{S}_{\rho}(h_{u}) ])$가 된다. 그런데 $\mathrm{val} \ge \frac{\cos^{-1}\rho}{\pi} + \varepsilon^{\prime}$이므로

$\mathbb{E}_{u}[ \mathcal{S}_{\rho}(h_{u}) ] \le 1 - \frac{2\cos^{-1}\rho}{\pi} - 2\varepsilon^{\prime}$이 성립한다.

 

이것만으로는 아무것도 안 나오고, 새로운 개념을 정의해야 한다.

 

Majority is Stablest Theorem and its variants

이 부분은 증명하지 않을 거기 때문에 설명이 다소 거칠다. 추후에 이해가 쌓이면 다시 다루는 것으로..

$f : 2^{[n]} \to \pm 1$에 대해, $i \in [n]$의 influence $\mathrm{Inf}_{i}(f) = \Pr[f(S) \neq f(S \oplus i)]$로 정의한다. 여기서 $S \oplus i$는 $i$가 $S$에 속하는 경우 빼고, 속하지 않는 경우 넣어주는 대칭차집합을 의미한다.

 

임의의 함수 $f, g : 2^{[n]} \to \mathbb{R}$에 대해 내적 $\left< f, g \right> = \mathbb{E} [fg] = \frac{1}{2^n} \sum_{S} f(S)g(S)$로 정의하자. 이 때 $f$의 fourier coefficient 를 $\hat{f}(S) = \frac{1}{2^n} \sum_{T} (-1)^{\lvert S - T \rvert} f(T)$로 정의하면, 몇 가지 성질이 성립함을 알 수 있다.

• $\left< f, g \right> = \sum_{S} \hat{f}(S)\hat{g}(S)$.
• 특히 $f : 2^{[n]} \to \pm 1$인 경우, $\mathrm{Inf}_{i}(f) = \sum_{i \in S} \hat{f}(S)^{2}$.

때문에 일반적인 함수에 대한 influence는 $\sum_{i \in S} \hat{f}(S)^{2}$로 정의한다.

 

$f(S) = (-1)^{\lvert S \rvert}$와 같은 parity function의 경우, 모든 $i$에 대해 $\mathrm{Inf}_{i}(f) = 1$로 높은 influence를 가지고 있다. majority is stablest theorem은 influence에 대한 global bound가 있다면 stability에 대한 bound를 준다.

 

Theorem. (Majority is stablest)

$f : 2^{[n]} \to [-1, 1]$에 대해, 임의의 $\rho \in [0, 1), \varepsilon > 0$에 대해 다음을 만족하는 $\delta > 0$이 존재한다.

 

"만약 $\mathbb{E}f = 0$, $\mathrm{Inf}_{i}(f) \le \delta$라면 $\mathcal{S}_{\rho}(f) \le 1 - \frac{2}{\pi}\cos^{-1}\rho + \varepsilon$."

 

오늘 사용할 버전은 이것의 응용 버전으로, $\rho$의 범위도 다르고 부등호 방향도 다르고 많은 것이 달라서 헷갈리지만 결과만 보면 된다.

 

$\mathrm{Inf}_{i}^{k}(f) := \sum_{i \in S, \lvert S \rvert \le k} \hat{f}(S)^{2}$를 $k$-degree influence of $i$로 정의한다.

 

Theorem. (Majority is stablest-variant)

$f: 2^{[n]} \to [-1, 1]$에 대해, 임의의 $\rho \in (-1, 0], \varepsilon > 0$에 대해 다음을 만족하는 $\delta > 0$, $k \ge 1$이 존재한다.

 

"만약 $\mathrm{Inf}_{i}^{k}(f) \le \delta$ 라면 $\mathcal{S}_{\rho}(f) \ge 1 - \frac[2}{\pi}\cos^{-1}\rho - \varepsilon$."

 

$\mathbb{E}f = 0$이라는 조건은 원문에 없다. 특히 우리가 사용할 예시에서는 강제되면 안된다.

 

Soundness Proof (Continued)

결국 돌고 돌아, $\mathbb{E}_{u}[ \mathcal{S}_{\rho}(h_{u}) ] \le 1 - \frac{2\cos^{-1}\rho}{\pi} - 2\varepsilon^{\prime}$이 성립한다는 사실에서 Majority is stablest의 대우를 생각할 수 있다. Markov's inequality를 사용하면, 최소한 $\frac{\varepsilon^{\prime}}{2}\lvert U \rvert$만큼의 $u$가 $\mathcal{S}_{\rho}(h_{u}) \le 1 - \frac{2\cos^{-1}\rho}{\pi} - \varepsilon^{\prime}$을 만족하고, 각 $u$에 대해서는 Majorist is stablest-variant에 따라 어떤 $j \in [k]$가 존재하여 $\mathrm{Inf}_{j}^{K}(h_{u}) \ge \delta$이다. 우리는 여기서 $l(u) = j$로 labeling하고 싶다.

 

여기서 잠깐, 왜 influence가 큰 label을 달아주고 싶을까? 간단히 말해 이게 가능한 $V$의 후보를 늘려주기 때문이다.

위에서 label된 $u$들을 $U$-good vertex라고 하자. $U$-good vertex가 아닌 $U$의 나머지 정점들은 아무렇게나 label해줄 것이다.

 

$\mathrm{Inf}_{j}^{K}(h_{u}) \ge \delta$에서 좌변을 열심히 전개하면,

$$\mathrm{Inf}_{j}^{K}(h_{u}) = \sum_{j \in S, \lvert S \rvert \le K} \hat{h_u}(S)^{2} = \sum_{j \in S, \lvert S \rvert \le K} \mathbb{E}_{v \in N(u)} [\hat{f_{v}}(\pi^{-1}(S))]^{2} \le \sum \mathbb{E} [ \hat{f_v}(\pi(S))^{2}] = \mathbb{E}[ \mathrm{Inf}_{\pi(j)}^{K} (f_v) ]$$

를 얻는다. $\mathbb{E}[X]^{2} \le \mathbb{E}[X^2]$를 쓰고, 기댓값과 합을 열심히 바꿔쳐주면 된다.

 

즉 $j$의 influence가 크다는 사실만으로, $N(u)$에 $\pi(j)$의 influence가 큰 정점들이 많다는 사실을 확인한 것이다. 역시 Markov's inequality를 통해 최소한 $\frac{\delta}{2}\lvert N(u) \rvert$만큼의 정점 $v$가 $\mathrm{Inf}_{\pi(j)}^{K} (f_v) \ge \frac{\delta}{2}$를 만족함을 알 수 있다. 이러한 정점들을 $V$-good한 정점들이라고 하면 역시 전체의 $\delta/2$ 이상이 $V$-good vertex들이..면 좋겠지만, 여러 $u$에 대해서 하나의 $v$로 이러한 "goodness"가 몰릴 수도 있다. 이 경우 $\pi(j)$ 중 하나로 labeling했을 때 수많은 unsatisfied edge들이 생길 수 있다.

 

하지만 $\sum_{i \in [k]} \mathrm{Inf}_{i}^{K} (f_{v}) = \sum_{\lvert S \rvert \le K} \lvert S \rvert \hat{f}(S)^{2} \le K \lVert f \rVert_{2}^{2} \le K$가 성립하므로, 한 정점 $v$에 대해 $U$-good vertex에서 induce되는 $V$-goodness는 최대 $K/(\delta/2) = 2K/\delta$개의 label에만 생긴다. 따라서 이 $2K/\delta$개의 후보 중 아무 label로 $v$를 마킹해준다.

 

따라서, 어떤 간선이 하필 $U$-good vertex $u$와 그 이웃 중 $V$-good vertex $v$여서 labeling에 의해 satisfy될 확률은 $\varepsilon = \frac{\varepsilon'}{2} \cdot \frac{\delta}{2} \cdot \frac{\delta}{2K}$가 된다. $K, \delta$는 $\varepsilon^{\prime}$의 함수로 나타나기 때문에 이로써 soundness의 증명이 끝난다.

 

Reference

- https://www.wisdom.weizmann.ac.il/~dinuri/courses/19-inapprox/lec6.pdf

- https://arxiv.org/pdf/1211.1001

- https://www.designofapproxalgs.com/book.pdf