koosaga's profile image

koosaga

April 17, 2020 00:00

FPT Inapproximability of Directed Multicut

graph-theory , complexity-theory

FPT Inapproximability of Directed Multicut

그래프의 연결성, 그리고 연결성을 변화시키는 방법 (그래프 절단) 은 알고리즘 연구의 극초창기부터 연구되었던 문제들이다. 그래프 절단은 냉전 초기 공중폭격으로 적국의 철도망을 파괴하는 군사적인 목적으로 연구가 시작되었다. 이후 반세기 이상 이러한 류의 문제는 그래프에 대한 최적화 문제 중 가장 기초적인 문제로 자리잡는다. 이 문제는 이론적으로도 다른 문제의 근간이 되며, 무수히 많은 현실적 계산 문제와 연관되어 있다.

그래프 절단 유형의 문제로는 크게 다음과 같은 4가지 종류가 있다. 이하 특정한 언급 없을 시, 그래프는 $n$ 개의 정점과 $m$ 개의 간선이 있으며, 각 간선에는 0 이상의 가중치와 방향성이 있다고 가정한다.

  • $s - t$ cut: $s \rightarrow t$ 로 가는 경로가 없게끔 간선을 지우는 문제이다. 방향 그래프에서 Maximum Flow를 사용하여 $O(nm)$ 에 해결할 수 있다.
  • Connectivity (Global Min-Cut): 그래프가 2개 이상의 weakly-connected component를 가지도록 간선을 지우는 문제이다. 일반성을 잃지 않고 무방향 그래프를 가정할 수 있다. 무방향 그래프에서는 랜덤 알고리즘을 사용하여 $O(m^{1 + \epsilon})$ 시간에 해결할 수 있다. 결정론적 알고리즘으로는 가중치가 1일 때 $O(m^{1 + \epsilon})$ 시간에 해결할 수 있고, 일반적인 경우에는 $O(nm)$ 시간에 해결할 수 있다.
  • Multiway cut: 그래프 상의 $K$ 개의 정점이 추가로 주어질 때, 임의의 서로 다른 두 정점 간에 경로가 없도록 하는 문제이다.
    • 무방향 그래프고 $K = 2$ 일 경우 이 문제는 $s - t$ cut 문제와 동일하다. 그 외 모든 경우 이 문제는 NP-hard이다.
    • 무방향 그래프에서는 1.2965-approximation 이 가능하다.
    • 방향 그래프에서는 2-approximation이 가능하며, Unique Games Conjecture를 가정할 경우 $2 - \epsilon$ approximation은 불가능하다.
    • 해집합의 크기가 $p$ 일 때 $p$ 에 대해 FPT이다.
  • Multicut: $K$ 개의 pair $(s_i, t_i)$ 가 주어질 때, 모든 pair에 대해 $s_i \rightarrow t_i$ 로 가는 경로가 없게끔 간선을 지우는 문제이다. Multiway cut, $s - t$ cut의 일반화이다.
    • $K = 1$ 일 경우 이 문제는 $s - t$ cut 문제와 동일하다.
    • 무방향 그래프에서 $K = 2$ 일 경우 다항 시간에 해결할 수 있다. 이를 Two-commodity flow라고 부른다. 이름에서 짐작할 수 있듯이, $K \le 2$ 인 경우 max-flow min-cut theorem이 성립한다. $K > 2$인 경우는 성립하지 않는다.
    • 방향 그래프에서 $K = 2$ 일 경우 Directed multiway cut으로 환원할 수 있다.
    • $K \geq 3$ 인 경우 NP-hard 이다.
    • 무방향 그래프에서는 $O(\log K)$ approximation, 방향 그래프에서는 $K$-approximation이 가능하다. 강한 Unique Games Conjecture를 가정할 경우 무방향 그래프에서 $O(\sqrt{\log \log n})-$approximation, Unique Games Conjecture를 가정할 경우 방향 그래프에서 $K - \epsilon$ approximation 은 NP-hard이다. 정확히 어떠한 강한 UGC 가 가정되는지는 다음 링크를 참고하라.
    • $p$ 에 대해 parametrized될 경우, 무방향 그래프에서는 2-approximation이, 방향 그래프에서는 $\lceil \frac{K}{2} \rceil$-approximation이 존재한다. 한편, Gap-ETH를 가정할 경우, $K \geq 4$ 에 대해서 $\frac{59}{58}$-approximation이 불가능하다.

이 글에서는, Gap-ETH를 가정할 경우, $p$ 에 대해 parametrize된 Directed Multicut with 4 Pairs 문제에 대한 $\frac{59}{58} - \epsilon$ approximation이 어려움을 소개한 논문을 정리한다. $K = 4$ 에서의 hardness 결과가 있기 때문에 이는 모든 $K \geq 4$ 에 대해서도 적용된다. 논문 원본에 비해서 간략하게 서술되거나 다른 방식으로 서술된 부분이 있을 수 있음에 주의하라.

Main Result

이 글에서는 다음과 같은 문제 COLORED-CLIQUE 를 정의한다.

  • Input: 무방향 그래프 $G$ 와, 정점 집합 $V(G)$ 의 partition $V_1, V_2, \ldots, V_l$
  • Goal: 다음과 같은 함수 $f : [l] \rightarrow V(G)$ 를 찾아야 한다.
    • $f(i) \in V_i$
    • $(f(i), f(j)) \in E(G)$ 인 ${i, j} \subseteq [l]$ 의 개수 최대화

어떠한 COLORED-CLIQUE 인스턴스 $\Gamma$ 에 대해서, 최적해의 $(f(i), f(j)) \in E(G)$ 인 ${i, j} \subseteq [l]$ 의 개수를 $\binom{l}{2}$ 로 나눈 값을 $val(\Gamma)$ 라고 정의한다. 예를 들어, 클리크를 찾았다고 하면 그 경우 $val(\Gamma) = 1$ 이 성립한다. 이제 다음과 같은 정리를 소개한다.

Theorem 1. Gap-ETH를 가정했을 때, 임의의 함수 $h(l) = o(1)$ 에 대해, COLORED-CLIQUE 인스턴스 $\Gamma$ 가 다음 두 경우 중 하나인지를 구분할 수 있는 $f(l) \times V(G) ^{O(1)}$ 시간 알고리즘은 존재하지 않는다:
  • (YES) $val(\Gamma) = 1$
  • (NO) $val(\Gamma) < l^{h(l) - 1}$

Remark. 만약 두 경우 중 하나에 속하지 않는다면 둘 중 아무 결과나 반환해도 된다.

Theorem 1의 증명은 이 글에서 다루지 않는다. 이제 다음 Lemma를 소개한다:

Lemma. COLORED-CLIQUE 인스턴스 $\Gamma$ 이 주어졌을 때, 다음과 같은 성질을 만족하는 DIRECTED MULTICUT WITH 4 PAIRS 인스턴스를 다항 시간에 구성할 수 있다:

  • (Completeness): 만약 $val(\Gamma) = 1$ 이면, $29l^2$ 이하의 비용을 가지는 해가 존재
  • (Soundness): 만약 $val(\Gamma) < 0.1$ 이면, $29.5l^2$ 초과의 비용을 가지는 해가 존재
  • (Parameter Dependency) 해의 크기 $p$는 $O(l^2)$ 임

다음 장부터의 내용은 온전히 이 Lemma를 증명하는 데 사용될 것이다. 고로 이 역시 지금은 증명하지 않는다. 이를 토대로 다음을 증명한다:

Theorem 2. Gap-ETH를 가정할 경우, $K = 4$ 에 대해서 $\frac{59}{58}$ approximation 을 찾는 $f(p) \times V(G) ^{O(1)}$ 알고리즘은 존재하지 않는다.

Proof. 이것이 존재한다고 가정하자. 이 알고리즘에 $29l^2$ 이하의 해를 가지는 DIRECTED MULTICUT WITH 4 PAIRS 인스턴스를 제공하면, 항상 $29.5l^2$ 이하의 해를 찾게 될 것이다. Lemma를 따라서 구성한 인스턴스를 이 알고리즘에 제시하면, $val(\Gamma) = 1$ 일 때는 $29.5l^2$ 이하의 해가 반환되고, $val(\Gamma) < 0.1$ 일 때는 $29.5l^2$ 초과의 해가 반환된다. $h(l) = 1 - \frac{log(10)}{log(l)}$ 이라 정의하면, $h(l) = o(1)$ 이고, $l^{h(l) - 1} = 0.1$ 이니 Theorem 1에서 제시된 알고리즘을 제시할 수 있다. $p = O(l^2)$ 이니, $g(l) = f(O(l^2))$ 라고 정의하면 시간 복잡도 역시 Theorem 1에서 제시된 것과 일관된다. Theorem 1은 그러한 알고리즘이 존재하지 않는다고 하였으니, 가정에 모순이 된다.

고로 Lemma가 성립하면 증명이 완성된다.

Proof of Lemma: Construction and Parameter Dependency

일반성을 잃지 않고 $ V_i $ 의 크기는 모두 동일하며 이것이 $n$ 이라고 하자 (차수가 0인 정점을 추가함으로써 이렇게 만들 수 있다.) 이제 $ V(G) = nl$ 이다. 이제 다음과 같은 DIRECTED MULTICUT WITH 4 PAIRS 인스턴스를 생성한다. 이 때 가중치는 정점에 매겨져 있다.

img1

img2

그래프의 정점들은 다음과 같이 분류한다.

  • light vertices 는 회색이며 가중치 $B = \frac{l^2}{\binom{l}{2}}$ 를 갖는다.
  • medium vertices는 녹색이며 가중치 $2B$ 를 갖는다.
  • heavy vertices는 주황색이며 가중치 $20l$ 을 갖는다.
  • super-heavy vertices는 흰색이며 가중치 $100l^2$ 를 갖는다. (실질적으로 무한이라고 간주하면 된다.)

이제 인스턴스를 설명한다.

  1. Multicut을 해결해야 하는 4개의 source-sink pair는 다음과 같다. 이들을 터미널 정점 이라 부른다. 8개의 터미널 정점은 super-heavy 하다.

${(s_{0\rightarrow n}^x, t_{0\rightarrow n}^x), (s_{0\rightarrow n}^y, t_{0\rightarrow n}^y), (s_{n\rightarrow 0}^{<}, t_{n\rightarrow 0}^{<}), (s_{n\rightarrow 0}^{>}, t_{n\rightarrow 0}^{>})}$

  1. 모든 $1 \le i \le l$ 에 대해 다음과 같이 $2n+1$ 개의 정점이 있는 양방향 경로 $Z_i$를 만든다. 이 경로를 z-path 라고 부른다. Figure 2를 참조하라. 경로 내의 정점은

$Z_i := z_0^{i} \leftrightarrow \hat{z}_1^{i} \leftrightarrow z_1^{i} \leftrightarrow \hat{z}_2^{i} \leftrightarrow \ldots \leftrightarrow \hat{z}_n^{i} \leftrightarrow z_n^{i}$

와 같이 라벨링한다. $z_a^i$ 는 super-heavy 하며 $\hat{z}_a^{i}$ 는 heavy 하다.

heavy 한 정점은 여기서만 등장하며, 끊을 수 있는 정점 중 가장 무거운 정점이다. 각 경로마다 이 정점이 정확히 하나씩 끊겨야 하기 때문에, 이 정점을 어떻게 끊는지는, $V_i$ 에서 어떠한 정점을 고를 것인지에 대한 선택과 일대일 대응된다고 볼 수 있다.

  1. 모든 $l(l-1)$ 개의 쌍 $(i, j)$ ($1 \le i, j \le l, i \neq j$) 에 대해 다음과 같이 $2n+1$ 개의 정점이 있는 두 개의 양방향 경로 $X_{i, j}, Y_{i, j}$를 만든다. 이 경로를 x-path, y-path 라고 부른다. Figure 1/2를 참조하라. 경로 내의 정점은

$X_{i, j} := x_0^{i,j} \leftrightarrow \hat{x}_1^{i,j} \leftrightarrow x_1^{i,j} \leftrightarrow \hat{x}_2^{i,j} \leftrightarrow \ldots \leftrightarrow \hat{x}_n^{i,j} \leftrightarrow x_n^{i,j}$

$Y_{i, j} := y_0^{i,j} \leftrightarrow \hat{y}_1^{i,j} \leftrightarrow y_1^{i,j} \leftrightarrow \hat{y}_2^{i,j} \leftrightarrow \ldots \leftrightarrow \hat{y}_n^{i,j} \leftrightarrow y_n^{i,j}$

과 같이 라벨링한다. $x_a^{i, j}, y_a^{i, j}$ 는 super-heavy 하며 $\hat{x}_a^{i, j}, \hat{y}_a^{i, j}$ 는 medium 하다. 그 다음, 모든 $1 \le i, j \le l, i \neq j, 0 \le a \le n$ 에 대해 $(x_a^{i, j}, z_a^i), (z_a^i, y_a^{i, j})$ 와 같은 방향 간선을 추가해 준다.

  1. 이제 터미널 정점들을 각 경로에 붙여준다. 이들은 그림에서 보라색 간선으로 표시되어 있다.
  • 모든 $l(l-1)$ 개의 쌍 $(i, j)$ ($1 \le i, j \le l, i \neq j$) 에 대해 $(s_{0\rightarrow n}^{x}, x_0^{i, j})$ 와 $(y_n^{i, j}, t_{0\rightarrow n}^{y})$ 간선을 추가한다.
  • 모든 $1\le i \le l$에 대해 $(s_{0\rightarrow n}^{y}, z_0^i)$ 와 $(z_0^i, t_{0\rightarrow n}^{x})$ 간선을 추가한다.
  • 모든 $\binom{l}{2}$ 개의 쌍 $(i, j)$ ($1 \le i < j \le l$) 에 대해 $(s_{n\rightarrow 0}^{<}, x_n^{i, j})$ 와 $(y_0^{i, j}, t_{n\rightarrow 0}^{<})$ 간선을 추가한다.
  • 모든 $\binom{l}{2}$ 개의 쌍 $(i, j)$ ($1 \le j < i \le l$) 에 대해 $(s_{n\rightarrow 0}^{>}, x_n^{i, j})$ 와 $(y_0^{i, j}, t_{n\rightarrow 0}^{>})$ 간선을 추가한다.

3/4번 point에 대해서는 Figure 2를 참고하면 좋다. Figure 2에서는 $1 \le i < j \le l$ 에 대해 $(s_{n\rightarrow 0}^{<}, x_n^{i, j})$ 와 $(y_0^{i, j}, t_{n\rightarrow 0}^{<})$ 간선을 추가한 모습을 보여준다. 그림으로는 나와있지 않지만, $1 \le j < i \le l$ 에 대해서도 동일한 형태의 그림을 상상할 수 있고, 이 때 $(s_{n\rightarrow 0}^{<}, t_{n\rightarrow 0}^{<})$ 는 $(s_{n\rightarrow 0}^{>}, t_{n\rightarrow 0}^{>})$ 로 대체된다.

  1. 모든 $\binom{l}{2}$ 개의 쌍 $(i, j)$ ($1 \le i < j \le l$) 에 대해, 사이클 없는 방향성 그리드 $P_{i, j}$ 를 만든다. 이를 p-grid 라고 부른다. Figure 1에서 x-path, y-path 에 둘러싸인 그리드가 $P_{i, j}$ 이다. $P_{i, j}$ 의 크기는 $n \times n$ 이며, 이 정점들은 row-major-order로 $p_{a, b}^{i, j}$ 와 같이 표시한다 $(1 \le a, b \le n$). 간선은 $(p_{a, b}^{i, j}, p_{a, b + 1}^{i, j}), (p_{a, b}^{i, j}, p_{a + 1, b}^{i, j})$ 와 같은 형태의 간선이 $2n(n-1)$ 개 존재한다. 만약 $v_a^i v_b^j \in E(G)$ 이면, $P_{i, j}^{a, b}$ 는 light, 그 외 경우 $P_{i, j}^{a, b}$ 는 super-heavy 하다. 그 다음, 모든 $1 \le a \le n$ 에 대해 $(x_a^{i, j}, p_{a, 1}^{i, j}), (p_{a, n}^{i, j}, y_{a-1}^{i, j}), (x_a^{j, i}, p_{1, a}^{i, j}), (p_{n, a}^{i, j}, y_{a - 1}^{i, j})$ 와 같은 형태의 방향성 간선을 추가해 준다. (Figure 1의 실선 간선을 참고)

여기서 다음과 같은 두 가지 사실이 증명된다:

  • 이 그리드는 자명히 다항 시간에 구성할 수 있다.
  • 모든 터미널 정점을 끊는 비용이 $800l^2$ 이다. 양의 가중치를 가진 정점 중 최소 가중치는 $B$ 이니, $400l(l-1)B = 800l^2$ 이니, 항상 해집합의 크기는 $p = O(l^2)$ 이다. 고로 Parameter Dependency가 증명된다.

Proof of Lemma: Completeness

COLORED-CLIQUE 인스턴스에서 $val(\Gamma) = 1$ 이라는 것은, 문제의 조건을 만족하는 크기 $l$ 의 클리크 $f(1), f(2), \ldots, f(l)$ 을 뽑을 수 있음과 동일하다. 이 클리크를 토대로 다음과 같은 정점 집합 $X$ 를 만들자.

$X = {\hat{x}{f(i)}^{i, j}, \hat{y}{f(i)}^{i, j} : 1 \le i, j \le l, i \neq j} \cup {\hat{z}{f(i)}^i : 1 \le i \le l} \cup {p{f(i), f(j)}^{i, j}: 1 \le i < j \le l}$

이 정점 집합에는 medium한 정점이 $2l(l-1)$ 개, heavy 한 정점이 $l$ 개, light한 정점이 $\frac{l(l-1)}{2}$ 개 있다. 마지막 집합의 Light함은 $l$ 이 클리크라는 정의에서 따라옴에 유의하라. 이를 위의 정의에 따라서 계산하면 $8l^2 + 20l \times l + l^2 = 29l^2$ 가 되어서, $X$ 의 비용이 $29l^2$ 임을 알 수 있다.

이제 $X$ 가 정의한 DIRECTED MULTICUT WITH 4 PAIRS 인스턴스의 해임을 증명한다. 먼저, 우리가 구성한 그래프에서 x, y, z-path 를 큰 줄기라고 두고 생각해 보면, Figure 2의 그림은 x-path -> z-path -> y-path 와 같이 방향 간선이 그어져 있다고 생각할 수 있고, Figure 1의 그림은 x-path -> p-grid -> y-path 와 같이 방향 간선이 그어져 있다고 생각할 수 있다. 이제 각각의 4가지 쌍에 대해서 경로가 없음을 증명한다.

  • $(s_{0 \rightarrow n}^{x}, t_{0 \rightarrow n}^{x})$ 쌍: Figure 2에 있는 정점만이 이 쌍을 잇는 경로의 경유점이 될 수 있다. 모든 $1 \le i, j \le l, i \neq j$ 에 대해 $\hat{x}{f(i)}^{i, j},\hat{z}{f(i)}^i$ 정점이 끊어져 있다. 고로 경로가 존재하지 않는다.
  • $(s_{0 \rightarrow n}^{y}, t_{0 \rightarrow n}^{y})$ 쌍: 모든 $1 \le i, j \le l, i \neq j$ 에 대해 $\hat{z}{f(i)}^i, \hat{y}{f(i)}^{i, j}$ 정점이 끊어져 있다. 고로 위와 동일한 이유로 경로가 존재하지 않는다.
  • $(s_{n\rightarrow 0}^{<}, t_{n\rightarrow 0}^{<})$ 쌍: Figure 1을 지나는 경로와 2를 지나는 경로를 따로 생각해 주자. Figure 2에 있는 정점을 지나는 경로는, $\hat{x}{f(i)}^{i, j}, \hat{z}{f(i)}^i, \hat{y}{f(i)}^{i, j}$ 가 끊겨 있어 위와 비슷한 이유로 경로가 존재하지 않는다. Figure 1에 있는 정점을 지나는 경로는, $\hat{x}{f(i)}^{i, j}, \hat{y}{f(i)}^{i, j}$ 가 끊겨 있어, 이를 피하려면 정확히 하나의 경로만이 존재하게 된다. (그림의 빨간 원에 색칠된 정점에 대응) 이 하나의 경로 상에 있는 정점 $p{f(i), f(j)}^{i, j}$ 가 $X$ 에 있기 때문에, 경로가 존재하지 않는다.
  • $(s_{n\rightarrow 0}^{>}, t_{n\rightarrow 0}^{>})$ 쌍: 일반성을 잃지 않고 위와 동일한 이유로 경로가 존재하지 않는다.

Proof of Lemma: Soundness

대우명제를 증명한다: 비용이 $29.5l^2$ 이하인 DIRECTED MULTICUT WITH 4 PAIRS 의 해 $S$ 가 주어질 때, $val(\Gamma) \geq \frac{1}{10}$ 임을 보인다.

Lemma 1.1. $S$ 에는 super-heavy vertex가 없다. (자명)

Lemma 1.2. 모든 $1 \le i \le l$ 에 대해 $ S \cap Z_i \geq 1$ (Figure 2 그림을 보면 자명하다.)
Lemma 1.3. 모든 $1 \le i, j \le l, i \neq j$ 에 대해 $ S \cap X_{i, j} \geq 1, S \cap Y_{i, j} \geq 1$ (Figure 2 그림을 보면 자명하다.)
Definition 1. 정수 $1 \le i \le l$ 에 대해, $ S \cap Z_i = 1$ 이면 이 정수를 good 하다고 한다. good한 정수 $i$ 에 대해 $g(i)$ 를 $S \cap Z_i$ 의 유일한 정점이라고 하자.
Lemma 1.4. $GOOD = {1 \le i \le l : i \text{ is good}}$ 이라고 정의하자. $ GOOD \geq \frac{37l}{40}$ 이다.
Proof of Lemma 1.4. Lemma 1.2에 의해 $20l^2$, Lemma 1.3에 의해 $8l^2$ 의 비용이 필요하다. $i \notin GOOD$ 일 때 $ S \cap Z_i \geq 2$ 이다. 이 모든 것을 반영하면 비용의 하한은 $28l^2 + (l - GOOD ) 20l$ 이다. $(l - GOOD )20l \le 1.5l^2$ 이니 Lemma가 증명된다.

Definition 2. $1 \le i < j \le l$ 에 대해서, 정수 쌍 $(i, j)$ 가 great 하다는 것은 $S$ 가 다음과 같음을 뜻한다:

  • $ X_{i, j} \cap S = 1$
  • $ X_{j, i} \cap S = 1$
  • $ Y_{i, j} \cap S = 1$
  • $ Y_{j, i} \cap S = 1$
  • $ P_{i, j} \cap S = 1$ ($P_{i, j}$ 는 $(i, j)$ 가 이루는 p-grid 의 정점 집합을 뜻함)

Lemma 1.5. $1 \le i < j \le l$ 에 대해서, 정수 $i, j$ 가 good 하며 $(i, j)$ 가 great하면, $v_{g(i)}^i - v_{g(j)}^j \in E(G)$ 이다.

Proof of Lemma 1.5. $\hat{z}{g(i)}^i$ 가 $Z_i$ 에서 끊긴 유일한 정점이고, $\hat{z}{g(j)}^j$ 가 $Z_j$ 에서 끊긴 유일한 정점이다. $X_{i, j}, X_{j, i}, Y_{i, j}, Y_{j, i}$ 에서 끊긴 유일한 정점들을 각각 $\hat{x}{i_1}^{i, j}, \hat{x}{i_2}^{i, j}, \hat{y}{j_1}^{i, j}, \hat{y}{j_2}^{i, j}$ 라고 하면, $1 \le i_1 \le g(i) \le i_2 \le n, 1 \le j_1 \le g(j) \le j_2 \le n$ 가 성립한다. $i_1 < i_2$ 혹은 $j_1 < j_2$ 일 경우 $P_{i, j}$ 에서 하나의 정점을 끊어서 cut을 만들 수 없음을 알 수 있다. 고로 $i_1 = i_2 = g(i), j_1 = j_2 = g(j)$ 이며 이는 $(g(i), g(j))$ 셀이 끊겼음을 뜻한다. 이 셀은 light하기 때문에, Lemma가 증명된다.

Definition 3. $1 \le i < j \le l$ 에 대해 $B_{i, j} = X_{i, j} \cup X_{j, i} \cup Y_{i, j} \cup Y_{j, i} \cup P_{i, j}$ 라고 하자.

Lemma 1.6. $1 \le i < j \le l$ 이며 $i, j \in GOOD$ 인 $i, j$ 에 대해, 둘 중 하나가 성립한다:

  • $(i, j)$ 가 great 하고 $B_{i, j}$ 의 가중치 합이 정확히 $9B$ 이다.
  • $B_{i, j}$ 의 가중치 합이 $10B$ 이상이다.

Proof of Lemma 1.6. $(i, j)$ 가 great 할 경우 정의에 따라 medium vertex가 4개, light vertex가 1개 사용된다. 고로 가중치 합이 $9B$가 된다. $(i, j)$ 가 great 하지 않을 경우 가중치는 $9B$ 를 초과하며 $B$ 의 배수이다. 고로 $10B$ 이상이 된다.

Lemma 1.7. $E = {1 \le i < j \le l: i, j \in GOOD, (i, j) \text{ is great}}$ 라고 하자. $ E \geq \frac{1}{10}\binom{l}{2}$ 이다.
Proof of Lemma 1.7. Lemma 1.2/1.3에서 $S \cap (X_{i, j} \cup Y_{i, j} \cup Z_i)$ 이 최소 $28l^2$ 의 비용을 가짐을 보였다. 고로 $S \cap P_{i, j}$ 에서 고른 정점의 비용 합은 최대 $1.5l^2$ 이고, 이에 따라 최대 $\frac{3}{2} \binom{l}{2}$ 개의 light 정점을 모든 $P_{i, j}$ 에서 고를 수 있다. $i, j \in GOOD$ 조건을 추가한 후 이 조건을 만족하는 $i, j$ 에 대해서만 생각하자. $(i, j)$ 가 great한 경우에는 1개를 고르고, 그 외에는 2개 이상을 고른다. 고로 $(\binom{37l/40}{2} - E ) \times 2 + E \le \frac{3}{2} \binom{l}{2}$ 가 만족된다. 계산하면 $ E \geq \frac{1}{10}\binom{l}{2}$ 임을 확인할 수 있다.

이제 다음과 같은 함수 $gg : [l] \rightarrow V(G)$ 를 정의하자:

$gg(i) = \begin{cases} g(i) &\quad\text{if }i \in GOOD
1 &\quad\text{otherwise.} \ \end{cases}$

$gg$ 를 $\Gamma$ 의 해라고 하면, Lemma 1.5와 Lemma 1.7에 의해 $val(\Gamma) \geq \frac{1}{10}$ 임이 증명된다.