Inapproximability in computational hardness

근사 알고리즘(Approximation algorithm)은, 문제에 대한 최적해를 제공하지는 못하나, 최적해에 근접한 해(근사해)를 빠른 시간에 찾는 알고리즘이다. NP-Complete인 문제들은 $P \neq NP$ 인 이상 최적해를 다항 시간에 구할 수 없는데, 이러한 문제를 회피하는 여러 방법 중 가장 많이 연구되는 방법 중 하나가 근사 알고리즘이다. 근사 알고리즘의 목표는, 최적해에 근접함이 보장된 해를 다항 시간에 찾는 것이며, 가능하다면 그 보장의 정도를 최대한으로 끌어오는 것이다.

모든 문제가 근사 알고리즘으로 쉽게 해결되었으면 정말 좋았겠지만 당연히 세상 일이 그렇게 되지는 않는다. 어떠한 문제들은 $P \neq NP$ 인 이상 최적해를 다항 시간에 구할 수 없을 뿐만 아니라, 근사 알고리즘 역시 다항 시간에 구할 수 없음이 알려져 있다. 근사 알고리즘이 만능이 아닌 이상, 이 역시 Hardness를 분석할 수 있는 방법이 필요할 것이다. 통상적인 결정 문제에서는 Polynomial-time reduction이라는 도구를 사용해서 Hardness를 분석하고 증명한다. 하지만 이러한 도구를 바로 근사 알고리즘에 적용하기에는 몇 가지 어려움이 있다. 그 중 가장 대표적인 문제는 근사 알고리즘은 최적해의 근접함 을 어느 정도로 유지하느냐에 따라서 어려움의 정도가 달라지는, 일종의 2차원적 성질을 가지고 있다는 점이다. 이 글에서는 근사 알고리즘에서 이러한 문제점을 해결하기 위해 어떠한 도구를 사용하는지를 알아보고, 그러한 도구를 통해서 증명할 수 있는 핵심적인 Hardness result들을 짚고 넘어간다.

Preliminaries

NP 문제는 해가 존재하는지 아닌지 여부를 판별하는 Decision problem으로 정의된다. 최적화 문제의 경우에도, 이 Decision problem의 해의 값 Threshold를 이분탐색하는 식으로 동일하게 다항 시간에 해결할 수 있기 때문에 NP의 정의를 사용할 수 있다. 하지만 추가적인 단계가 필요하기 때문에 다소 번잡한 것이 사실이고, 최적해의 크기에 대한 비율을 논의하는 Approximation algorithm을 다룰 때에는 특히 그렇다. 이러한 불편함을 해결하기 위해 NP-optimization problem (NPO problem) 을 다음과 같이 정의한다:

• 모든 해가 다항 시간 크기를 가지며 그 정당성이 다항 시간에 판별 가능하다.
• 모든 해의 비용을 다항 시간에 계산할 수 있다.

편의상 이후 "문제" 라 하면 모두 NPO problem을 뜻한다. 비용의 최소화가 목적이면 min-problem (최소화 문제), 최대화가 목적이면 max-problem (최대화 문제) 라고 한다.

어떠한 문제 $A$ 에 대해, Polynomial Time Approximation Scheme (PTAS)이 존재한다는 것은 다음과 같은 사실을 의미한다:

• $A$ 가 min-problem이라면, 임의의 입력 $x$ 과 상수 $\epsilon > 0$ 에 대해서, $(1 + \epsilon)OPT(x)$ 이하 크기의 해를 다항 시간에 찾을 수 있다.
• $A$ 가 max-problem이라면, 임의의 입력 $x$ 과 상수 $\epsilon > 0$ 에 대해서, $(1 - \epsilon)OPT(x)$ 이하 크기의 해를 다항 시간에 찾을 수 있다.

$OPT(x)$ 는 $x$ 라는 입력에 대한 최적해를 뜻한다. $\epsilon$ 이 상수로 가정되기 때문에, $\epsilon$ 에 대해서 극히 큰 함수 (예를 들어 $n^{(1/\epsilon)^{1/\epsilon}})$ 가 적용된다 하더라도 다항 시간 알고리즘으로 간주된다. 이제 다음과 같은 복잡도 클래스를 정의한다:

• $\text{PTAS}$ 는 PTAS가 존재하는 문제들의 집합이다.
• 최소화 문제 $A \in \text{APX}$ 라 함은, 어떠한 $c \geq 1$ 이 존재하여 $c\times OPT(x)$ 이하의 해를 다항 시간에 찾을 수 있음을 뜻한다. 최대화 문제의 경우 기준은 $\frac{1}{c} \times OPT(x)$ 이다.
• 최소화 문제 $A \in \text{Log-APX}$ 라 함은, 어떠한 $c \geq 1$ 이 존재하여 $c \log x \times OPT(x)$ 이하의 해를 다항 시간에 찾을 수 있음을 뜻한다. 최대화 문제의 경우 기준은 $\frac{1}{c \log x} \times OPT(x)$ 이다.
• 최소화 문제 $A \in \text{Poly-APX}$ 라 함은, 어떠한 다항식 $p$ 가 존재하여 $p(x) \times OPT(x)$ 이하의 해를 다항 시간에 찾을 수 있음을 뜻한다. 최대화 문제의 경우 기준은 $\frac{1}{p(x)} \times OPT(x)$ 이다.

$P \neq NP$ 를 가정하면 다음과 같은 사실이 참이다:

• $\text{TSP} \notin \text{Poly-APX}$
• $\text{CLIQUE} \in \text{Poly-APX}- \text{Log-APX}$
• $\text{SET-COVER} \in \text{Log-APX} - \text{APX}$
• $\text{MAX-3SAT} \in \text{APX} - \text{PTAS}$

즉, 위에서 서술한 네 클래스 중 완전히 같은 클래스는 없다.

APX-Hard and APX-Complete

너무나도 잘 알려진 Cook-Levin Theorem을 다시 한번 생각해 보자:

Cook-Levin Theorem. 3-SAT 문제는 NP이며, 모든 다른 NP 문제를 3-SAT으로 다항 시간에 reduction할 수 있다.

이와 비슷하게, Approximation algorithm에서 다루는 각각의 복잡도 클래스에 대해서 complete, hard 한 문제들을 정의하고, 문제들 간의 Reduction을 제시하는 것이 이번 글의 목표이다.

이를 위해서는 Reduction을 정의해야 할 것이다. 위에서 정의한 복잡도 클래스는 (PTAS 외) 모두 approximation factor의 상수항을 무시한다. 고로, 예를 들어 "$P$ 에 대해 $c$-approximation이 있다면 $Q$ 에 대해 $2c$-approximation이 있다" 와 같은 논의를 할 수 있다면 그것이 NP에서의 Polynomial time reduction에 대응되는 개념이 될 것이다. 이를 더 Formal하게 정의해 보자.

Definition 10.5. $A, B$ 를 두 개의 최적화 문제라고 하자. $A$ 에서 $B$ 로 가는 approximation preserving reduction (APR) 은 다음 성질을 만족하는, 다항 시간에 계산 가능한 함수 $(f, g)$ 의 쌍이다:

• $A$ 의 입력 $x$ 에 대응되는 $B$ 의 입력 $x^\prime = f(x)$ 이 항상 존재한다.
• 문제 $B$ 에 대한 입력 $x^\prime$ 의 해 $y$ 가 주어질 때, $y^\prime = g(x, y)$ 는 문제 $A$에 대한 입력 $x$ 의 해이다.
• $y^\prime$는 $y$ 와 비슷하게 좋은 해 이다. 이 비슷한 정도 가 어떤지에 따라서 세부적인 Reduction이 결정된다. 다음과 같은 예시가 있다:
  • PTAS reduction 은, 임의의 $\epsilon > 0$ 에 대해서, 무한으로 가는 증가함수 $\delta(\epsilon) > 0$이 존재하여, 만약 $y^\prime$ 이 $B$ 에 대한 $(1 + \delta(\epsilon))$-approximation 이라면, $y$ 가 $A$ 에 대한 $(1 + \epsilon)$-approximation 이어야 한다.
  • Strict reduction 은, $\delta(\epsilon) = \epsilon$ 인 PTAS reduction 이다.
  • APX reduction 은, $\delta(\epsilon) = O(\epsilon)$ 인 PTAS reduction 이다.

정의에서 이해할 수 있겠지만 APR 자체는 수학적 정의가 아니고 일종의 umbrella term이다. 결국 비슷한 정도로 좋은 해 에 대한 세부적인 정의가 각 Reduction의 성질을 보여준다고 생각하면 된다. 잠시 맨 처음 든, "$P$ 에 대해 $c$-approximation이 있다면 $Q$ 에 대해 $2c$-approximation이 있다" 의 예시를 살펴보면 이 예시는 APX Reduction 및 PTAS Reduction의 정의에 부합하지만, Strict reduction의 정의에는 부합하지 않는다. PTAS-reduction은 PTAS membership을 보존하고, APX-reduction은 APX membership (및 PTAS membership) 을 보존함이 자명하다.

Definition 10.9.

• 어떠한 문제 $B$가 APX-hard 라는 것은, MAX-3SAT에서 $B$ 로 가는 APX reduction이 존재함을 뜻한다.
• 어떠한 문제 $B$가 APX-complete 라는 것은, $B$ 가 APX-hard이며 $B \in \text{APX}$ 임을 뜻한다.

이 정의를 Cook-Levin Theorem과 비교해보면:

• NP가 APX에 대응되고
• Poly-time reduction이 APX reduction에 대응되고
• 3SAT이 MAX-3SAT에 대응됨

을 관찰할 수 있다.

Preliminaries에서 $\text{P} \neq \text{NP}$ 일 시 $\text{MAX-3SAT} \in \text{APX} - \text{PTAS}$ 임을 밝혔다. 이 사실을 사용하여, 다음과 같은 사실을 쉽게 보일 수 있다.

Theorem 10.10. $B \in \text{APX-Complete}$ 일 경우

• $B \in \text{APX}$
• $B \in \text{PTAS}$ 일 경우 $\text{P} = \text{NP}$.

PTAS reduction과는 다른 형태의 reduction인 L-reduction 이 존재한다. PTAS reduction보다 사용하기 편하기 때문에 이후 글에서 자주 사용할 것이다.

Definition 10.12. $A$ 에서 $B$ 로의 L-reduction은 다음 조건을 만족하는 APR이다:

• $OPT_B(x^\prime) = O(OPT_A(x))$
• $|cost_A(y) - OPT_A(x)| = O(|cost_B(y^\prime) - OPT_B(x^\prime)|)$
  이를 이제부터 $A \leq_{L} B$ 라 표현한다.

Theorem 10.13. $A \leq_{L} B$ 일 경우 $A$ 에서 $B$ 로 가는 APX reduction이 존재한다.
Proof. 편의상 Minimization case만을 논의한다 (Maximization에서도 동일하게 하면 된다). 우리가 보이고 싶은 것은 임의의 $\epsilon$ 에 대해 다음을 만족하는 상수 $\gamma > 0$ 가 존재한다는 것이다:

$cost_B(y^\prime) \le (1 + \gamma \epsilon) OPT_B(x^\prime) \rightarrow cost_A(x) \le (1 + \epsilon) OPT_A(x)$.

정의에 의해 다음 두 수식을 만족하는 상수 $\alpha, \beta > 0$ 이 존재한다:

• $OPT_B(x^\prime) \le \alpha OPT_A(x)$
• $(cost_A(y) - OPT_A(x)) \le \beta (cost_B(y^\prime) - OPT_B(x^\prime))$

고로
$(cost_A(y) - OPT_A(x)) \le \beta \gamma \epsilon OPT_B(x^\prime) \le \alpha \beta \gamma \epsilon OPT_A(x)$

$cost_A(y) \le (1 + \alpha \beta \gamma \epsilon) OPT_A(x)$

$\gamma = \frac{1}{\alpha \beta}$ 가 존재한다.

Exercise 10.14. $A \leq_{L} B, B \leq_{L} C$ 일 경우 $A \leq_{L} C$ 이다.
Proof. 역시 모두 최소화 문제라고 가정한다. 정의에 의해 다음 두 수식을 만족하는 상수 $\alpha_1, \alpha_2, \beta_1, \beta_2 > 0$ 가 존재한다:

• $OPT_B(x^\prime) \le \alpha_1 OPT_A(x)$
• $(cost_A(y) - OPT_A(x)) \le \beta_1 (cost_B(y^\prime) - OPT_B(x^\prime))$
• $OPT_C(x^{\prime\prime}) \le \alpha_2 OPT_B(x^\prime)$
• $(cost_B(y^\prime) - OPT_B(x^\prime)) \le \beta_2 (cost_C(y^{\prime\prime}) - OPT_C(x^{\prime\prime}))$

정리하면:

• $OPT_C(x^{\prime\prime}) \le \alpha_2\alpha_1 OPT_A(x)$
• $(cost_A(y) - OPT_A(x)) \le \beta_1 \beta_2 (cost_C(y^{\prime\prime}) - OPT_C(x^{\prime\prime}))$

고로 $A \leq_L C$ 이다.

Max 3SAT, its variants, and graph counterparts

MAX-3SAT 문제를 사용하여 우리는 APX-hard, APX-complete 를 정의하였다. 이제는 APX-complete 문제들의 예시를 더 찾아보면서 클래스에 대한 통찰을 넓힐 것이다. 우리는 MAX-3SAT 문제에 몇 가지 제약을 더 건, 쉬운 변형들을 살펴보고, 이 문제들 역시 모두 APX-complete 임을 보일 것이다.

Definition (MAX-3SAT). 모든 clause가 $\le 3$ 개의 literal을 가진 formula가 주어질 때, 만족 가능한 clause 수의 최댓값을 계산하여라.
Definition (MAX-3SAT-E$a$). 모든 clause가 $\le 3$ 개의 literal을 가지고, 각 변수가 최대 $\le a$ 번 등장하는 formula가 주어질 때, 만족 가능한 clause 수의 최댓값을 계산하여라.
Definition (MAX-2SAT). 모든 clause가 $\le 2$ 개의 literal을 가진 formula가 주어질 때, 만족 가능한 clause 수의 최댓값을 계산하여라.
Definition (MAX-NAE-3SAT). 모든 clause가 $\le 3$ 개의 literal을 가진 formula가 주어질 때, 어떠한 clause도 모든 literal이 참이 되지 않게 하면서, 만족 가능한 clause 수의 최댓값을 계산하여라.

이 단락에서는 정말 많은 Theorem을 보일 것이다. 그 중 첫 번째 Theorem은 MAX-3SAT-E$a$에 관련되어 있으며, 다음과 같다.

Theorem 10.18.

1. $\text{MAX-3SAT} \leq_L \text{MAX-3SAT-E7}$
2. $\text{MAX-3SAT-E7} \leq_L \text{MAX-3SAT-E3}$ (이 내용은 아마 배운 내용으로는 증명하기 불충분할 것이다. 여기서는 증명을 생략한다.)
3. $\text{MAX-3SAT-E3} \leq_L \text{MAX-3SAT}$

Corollary 10.18.

• $\text{MAX-3SAT} \leq_L \text{MAX-3SAT-E3}$ (Implied by transitivity from Exercise 10.14)
• $\text{MAX-3SAT-E3}$ 은 APX-complete이다. (Definition 10.9 및 $\text{MAX-3SAT} \in \text{APX}$.)

Theorem을 증명하기 앞서서 몇 가지 Lemma가 필요하다.

Lemma 10.15. $C$ 개의 clause를 가진 3SAT formula가 주어질 때, $O(C)$ 개 이상의 clause를 만족시키는 배정이 존재한다.
Proof. 각 clause는 1개 이상, 3개 이하의 서로 다른 변수로 구성되어 있다. 고로 모든 변수에 대해서 랜덤하게 배정했을 때, 각 clause가 참으로 계산될 확률은 최소 $0.5$ 이다 (clause에 단 하나의 변수가 있을 때이가 최악이고, 3개의 변수가 있다면 $0.875$ 가 된다). 기댓값의 선형성에 의해, 참이 되는 clause의 기댓값은 $0.5C$ 이다. 고로 $0.5C$ 개 이상의 clause를 만족시키는 배정이 존재한다.

Definition (Expander Graph). $d \in \mathbb{N}$ 에 대해서, $d$-expander graph $G = (V, E)$ 는 모든 정점의 차수가 $d$ 이며, 모든 정점의 이분할 $V = V_1 \cup V_2$ 에 대해 $V_1$ 과 $V_2$ 사이를 잇는 간선의 수가 $min(|V_1|, |V_2|)$ 이상이다.

Lemma 10.17. 모든 $k \equiv 0 \text{ (mod } 2)$ 에 대해, $k$ 개의 정점을 가진 $3$-expander 가 존재한다.
Remark. 이전에 블로그에서 Expander decomposition 을 소개할 때 사용했던 정의랑은 조금 다르다. Expander graph의 정의는 저자와 용례에 따라서 조금씩 다를 수 있으니 주의하는 것이 좋다. 어떠한 정의를 사용하건간에 "well-connected sparse graph" 인 것이 Expander graph의 골자이다.
Mea Culpa. 이 Lemma의 증명을 찾지 못하였기 때문에 사실이라고 자신 있게 소개하기 어렵다. 하지만 이 Lemma가 거짓이라고 하더라도 큰 틀에서 Theorem 10.18의 증명이 깨지지는 않는다는 증거가 여럿 있다. 예를 들어, 다음 글 의 Lemma 2.2에 따르면, 어떠한 상수 $C_1 \geq 1$ 이 존재하여, 임의의 양의 정수 $n$ 에 대해 $m \in [n, C_1 n]$ 개의 정점을 가진 14-regular graph $G = (V, E)$ 이 존재한다. 이 "사실" - 을 토대로 후술할 증명을 $\text{MAX-3SAT-E7}$ 대신 $\text{MAX-3SAT-E29}$ 에 적용하는 것은 어렵지 않다. 자세한 걸 알아보려면 expander graph의 이론에 익숙해야 하는 것 같은데 본인의 능력으로는 부족한 것 같다. 나는 잘 모르겠으니 이 글의 진실성에 염려되는 부분이 있다면 이 기회에 직접 탐구해 보는 것도 좋을 것 같다.

이제 증명을 시작한다.

Proof of Theorem 10.18.1. 모든 변수가 짝수번 등장한다고 가정하자 (그렇지 않다면 $x_i \lor \lnot x_i \lor \lnot x_i$ 등을 추가하면 될 것이다). $8$ 번 이상 등장하는 모든 변수 $x$에 대해 다음과 같이 변환한다:

• $x$ 가 $k$ 번 등장한다고 하면 $z_1, \ldots, z_k$ 라는 새로운 변수를 만들고 모든 $x$ 의 occurence를 $z_1, \ldots, z_k$ 로 대체한다.
• $G$ 를 $k$ 개의 정점을 가진 3-expander graph 라고 하자 (Thm 10.17에 의해 존재). 모든 간선 ${i, j}$ 에 대해 clause $(z_i \rightarrow z_j), (z_j \rightarrow z_i)$ 를 추가한다. 그래프의 차수가 정확히 $3$ 이기 때문에, 각 $z_i$ 가 정확히 7번 등장함을 관찰할 수 있다.

이로서 MAX-3SAT-E7 에 대응되는 인스턴스 $x^\prime$ 을 만들었다. 이 인스턴스에 대한 해 $y^\prime$에서 원래 인스턴스의 해 $y$ 를 이끌어내는 법을 논의하자. 우리가 원하는 상황은 $z_1, \ldots, z_k$ 이 $y^\prime$ 에서 모두 같은 값으로 배정되어 있는 것인데, 실제로는 그렇지 않을 수 있다. 고로 $z_i$ 에 대한 참/거짓 배정 중, 등장 횟수가 많은 쪽을 선택하자 (같을 경우 아무거나).

여기서 중요한 사실을 증명할 수 있는데, 인스턴스 $x^\prime$ 의 최적해 중 $z_i$ 에 대한 배정이 모두 동일한 것이 존재한다. $Z_{TRUE}$ 를 $z_i$ 에 참이 배정된 집합, $Z_{FALSE}$ 를 $z_i$ 에 거짓이 배정된 집합이라고 하고, 일반성을 잃지 않고 $|Z_{TRUE}| \geq |Z_{FALSE}| \geq 1$ 이라 하자. $Z_{FALSE}$ 에서 $Z_{TRUE}$ 로 가는 간선은 최소 $|Z_{FALSE}|$ 개 존재하며, 고로 현재 Expander graph에서 $|Z_{FALSE}|$ 개의 clause가 만족되지 않고 있다. 이들을 모두 True로 바꾸게 되면, 해당 개수만큼의 clause를 새롭게 만족시킨다. 한편, 각각의 $z_i$ 는 Expander graph가 아닌 곳에서 단 한번 등장했기 때문에 최대 $|Z_{FALSE}|$ 개의 clause가 새롭게 만족되지 않는다. 고로 $z_i$ 의 대한 배정이 동일하지 않다면, 그러한 최적해로 바꿔줄 수 있다.

이제 이상의 reduction이 $L$-reduction임을 증명하면 된다. 몇 가지를 보일 수 있다.

• $OPT_B(x^\prime) = O(OPT_A(x))$: Lemma 10.15의 결과로 유도할 수 있다. $x$ 가 $C$ 개의 Clause를 가진다면, $O(OPT_A(x)) = O(C)$ 이고, $x^\prime$ 역시 $O(C)$ 개의 Clause를 가지니, $OPT_B(x^\prime) = O(C)$ 이다.
• $OPT_A(x) + 3\sum_i k_i \le OPT_B(x^\prime)$: $z_i = x$ 로 동일하게 배정할 경우 새로 추가한 모든 Clause가 만족된다.
• $OPT_A(x) + 3\sum_i k_i \ge OPT_B(x^\prime)$: $OPT_B(x^\prime)$ 의 최적해는 모든 $z_i$ 에 대한 배정이 동일하다 가정할 수 있으니 그대로 $A$ 의 최적해로 사용하면 된다.
• $cost_A(y) + 3\sum_i k_i \ge cost_B(y^\prime)$: $y^\prime$ 을 위에서 설명한 방법대로 transform할 경우 항상 비용이 좋아진다. 그 이후에는 $z_i$ 에 대한 배정이 동일하니 그대로 $A$ 의 최적해로 사용하면 된다.

식을 정리하면

$OPT_A(x) + 3\sum_i k_i = OPT_B(x^\prime)$
$0 \ge cost_A(y) - OPT_A(x) \ge cost_B(y^\prime) - OPT_B(x^\prime)$
$|cost_A(y) - OPT_A(x)| = O(|cost_B(y^\prime) - OPT_B(x^\prime)|)$ $\blacksquare$.

Proof of Theorem 10.18.3. MAX-3SAT-E3 의 올바른 입력은 MAX-3SAT 의 올바른 입력이니 자명하다.

이제 $\text{MAX-3SAT-E3}$ 에 대한 분석을 끝냈으니, 이 사실을 사용하여 몇 가지 그래프 문제에 대한 Hardness를 증명한다. 다룰 문제들은 다음과 같다:

• $\text{INDEPENDENT SET-}a$ 는 모든 정점의 차수가 $\le a$ 인 그래프가 주어질 때 최대 독립 집합의 크기를 반환한다.
• $\text{VERTEX COV-}a$ 는 모든 정점의 차수가 $\le a$ 인 그래프가 주어질 때 최대 독립 집합의 크기를 반환한다.
• $\text{MAXCUT}$ 은 그래프가 주어질 때, $V = V_1 \cup V_2$ 인 이분할 $(V_1, V_2)$ 중 $V_1$ 과 $V_2$ 사이를 잇는 최대 간선의 개수를 반환한다.

다음 사실을 증명한다:

Theorem 10.22 다음과 같은 사실이 모두 참이다. 편의상 $P \neq NP$ 를 가정한다.

1. $\text{MAX-3SAT-E3} \le_L \text{INDEPENDENT SET-}4$
2. 모든 $\Delta \geq 4$ 에 대해 $\text{INDEPENDENT SET-}\Delta$ 는 APX-Complete이다.
3. $\text{INDEPENDENT SET-}4 \le_L \text{MAX-2SAT}$
4. $\text{MAX-2SAT} \le_L \text{MAX-NAE-3SAT}$
5. $\text{MAX-NAE-3SAT} \le_L \text{MAX-CUT}$
6. $\text{MAX-CUT} \in \text{APX} - \text{PTAS}$. 이는 또한 MAX-CUT 이 APX-Complete 임을 증명한다.

Proof of Theorem 10.22.1. 수식 $x$ 가 주어졌을 때 다음과 같이 그래프 $x^\prime$ 을 만든다:

• 각 literal이 등장할 때마다 정점을 하나씩 만든다. (즉 $x_i$ 가 여러번 등장하면 각각 따로 만든다).
• clause $L_1 \lor \ldots \lor L_n$ $(n\le 3)$ 에 대해서, 모든 $L_i$ 와 $L_j$ 간에 간선을 잇는다. (각 정점의 차수가 최대 2 증가한다.)
• 모든 변수 $x_i$ 에 대해, $x_i, \lnot x_i$ 형태의 정점 쌍에 간선을 잇는다. (E3이기 때문에 각 정점의 차수가 최대 2 증가한다.)

이 인스턴스에 대한 해 $y^\prime$ 이 주어졌을 때, 이 해에서 $x_i, \lnot x_i$ 형태의 정점이 같이 켜져 있는 경우는 없다. 만약 $x_i$ 형태의 정점이 켜져 있다면 이를 참으로 배정하고 그렇지 않다면 거짓으로 배정하자. 이렇게 해서 assignment $y$ 를 얻을 수 있다.

이제 다음을 관찰하자:

• Clause의 assignment는 독립 집합에 대응되고 독립 집합은 Clause의 assignment에 대응되니 $OPT_A(x) = OPT_B(x^\prime)$.
• $cost_A(y) \geq cost_B(y^\prime)$.
• $0 \ge cost_A(y) - OPT_A(x) \ge cost_B(y^\prime) - OPT_B(x^\prime)$

고로 이는 $L$-reduction이다.

Proof of Theorem 10.22.2. Theorem 10.22.1에 의해 Approximation algorithm만 얻으면 된다. 그래프가 비지 않을 때까지, 최소 차수의 정점을 고르고, 그래프에서 고른 정점과 인접한 정점들을 모두 지우는 것을 반복하는 그리디 알고리즘을 생각해 보자. 이 알고리즘은 항상 $\frac{N}{\Delta + 1}$ 개 이상의 답을 찾으니, $(\Delta + 1)$-approximation이 된다. 고로 $\text{INDEPENDENT SET-}\Delta \in \text{APX}$ 이다. 특별히 필요는 없지만, Halldorsson-Radhakrishnan 의 1997년 논문에서, 이 그리디 알고리즘이 $\text{INDEPENDENT SET-}\Delta$ 에 대한 $\frac{\Delta + 2}{3}$-approximation임을 증명한다.

Proof of Theorem 10.22.3 모든 정점의 차수가 $4$ 이하인 그래프 $x$ 가 주어졌을 때 다음과 같이 2-CNF 수식 $x^\prime$을 만든다:

• 모든 정점 $v$ 에 대해 clause ${v}$ 를 추가한다.
• 모든 간선 $(u, v)$ 에 대해 clause ${\lnot u \lor \lnot v}$ 를 추가한다.

이 인스턴스에 대한 assignment $y^\prime$ 이 주어질 때 이를 독립 집합으로 변환한다. 목표는 $v$ 가 참인 정점들을 독립 집합이라고 선언하는 것이다. 하지만, 간선 $(u, v)$ 에 대한 clause가 만족되지 않을 수 있는 것이 문제다. 만약 ${\lnot u \lor \lnot v}$ 형태의 clause 중 만족되지 않은 것이 있다면, $u = \text{FALSE}$ 로 두어 clause를 만족시키자. 이렇게 할 경우 satisfy가 되지 않는 clause는 ${u}$ 밖에 없기 때문에, 해가 나빠지지 않는다. 이제 문제가 해결되었으니 $v$ 가 참인 정점들을 독립 집합이라고 선언하면 된다.

이제 다음을 관찰하자:

• 독립 집합은 Clause의 Optimal assignment에 대응되니 $OPT_A(x) + |E(x)| = OPT_B(x^\prime)$
• Bounded degree와, Theorem 10.22.2의 증명에 나온 그리디 알고리즘에 의해, $OPT_A(x) = \Theta(|V(x)|)$ 이며 $|E(x)| = \Theta(|V(x)|)$. 고로 $OPT_B(x^\prime) = O(OPT_A(x))$.
• $cost_A(y) \geq cost_B(y^\prime)$.
• $0 \ge cost_A(y) - OPT_A(x) \ge cost_B(y^\prime) - OPT_B(x^\prime)$

고로 이는 $L$-reduction이다.

Proof of Theorem 10.22.4. 2-CNF 수식 $x$ 가 주어졌을 때 다음과 같은 수식 $x^\prime$ 을 만든다:

• $z$ 라는 새로운 변수를 만든다.
• 모든 clause에 $\lor z$ 를 넣는다.

이 인스턴스에 대한 assignment $y^\prime$ 이 주어질 때 이를 $x$ 에 대한 assignment $y$ 로 변환한다. 만약 $z = \text{FALSE}$ 면 $z$ 를 빼도 $cost_A(y) = cost_B(y^\prime)$ 이니 그대로 사용하면 된다. $z = \text{TRUE}$ 라면, 만족된 clause들 중에서는 false가 배정된 경우가 무조건 하나 이상 존재한다. 고로 $z$ 를 제외한 모든 clause의 결과를 뒤집고 사용하면, $cost_A(y) = cost_B(y^\prime)$ 이다. Optimal assignment에 대해서도 비슷한 이야기를 할 수 있고 결론적으로 $L$-reduction 을 얻는다.

Proof of Theorem 10.22.5. MAX-NAE-3SAT의 각 Clause에 중복된 원소가 없고, 1-clause가 없음을 가정하자. (이렇게 하여도 Theorem 10.22.4의 Specification과 모순이 없다.)

수식 $x$ 가 주어졌을 때 다음과 같은 그래프 $x^\prime$ 을 만든다. $x^\prime$에는 중복 간선이 있을 수 있음을 유념하라.

• 모든 변수 $x$ 에 대해, $x, \lnot x$ 라는 정점을 만들고, $k_i = 2 \times $($x, \lnot x$ 의 등장 횟수 합)만큼 두 정점간에 중복 간선을 추가해준다.
• clause $L_1 \lor L_2 \lor L_3$ 에 대해서, 모든 $L_i$ 와 $L_j$ 간에 간선을 하나 잇는다.
• clause $L_1 \lor L_2$ 에 대해서, $L_1$, $L_2$ 간에 간선을 두개 잇는다.

이 인스턴스에 대한 정점 이분할 $y^\prime = (V_1, V_2)$ 가 주어질 때 이를 $x$ 에 대한 assignment $y$ 로 변환한다. 만약 $x, \lnot x$ 가 같은 사이드에 있지 않다면 assignment $y$ 가 비교적 명확히 드러난다. 그렇지 않을 경우가 문제인데, Clause에 의해서 생기는 간선은 각 등장마다 정확히 $2$개이기 때문에, 중복 간선의 개수보다 항상 작거나 같다. 고로 정점 $x, \lnot x$ 가 같은 사이드에 있다면, 그 중 임의로 하나를 다른 사이드로 배정할 경우 답이 나빠지지 않는다. 이렇게 한 이후 $x \in V_1$ 인 변수들에 대해서 참을 배정하면 된다.

이제 다음을 관찰하자:

• 각 Clause에 1-clause가 없고 중복된 원소가 없기 때문에, clause 하나만을 만족시키는 assignment는 항상 존재한다. 고로 MAX-NAE-3SAT 역시 Randomization을 통해서 $O(|C|)$ 크기의 해를 찾을 수 있다. $\sum k_i = O(|C|)$ 이니 $OPT_B(x^\prime) = O(OPT_A(x))$.
• NAE Clause 하나는 Max Cut 상의 2개의 간선에 기여한다. 또한 $x, \lnot x$ 사이의 중복 간선은 모두 Max Cut에 들어가게 된다. 고로 $OPT_A(x) \times 2 + \sum k_i \le OPT_B(x^\prime)$
• Max Cut의 최적해는 중복 간선을 모두 사용하며, 각 NAE Clause에 대해서 2개의 간선을 사용하거나 사용하지 않는다. 우리의 변환 과정에 의해, 2개의 간선을 사용한 NAE Clause는 모두 만족되며, 그렇지 않은 NAE Clause는 만족되지 않는다. 고로 $OPT_A(x) \times 2 + \sum k_i \ge OPT_B(x^\prime)$
• $cost_A(y) \times 2 + \sum k_i \ge cost_B(y^\prime) $

정리하면
$cost_A(y) \times 2 + OPT_B(x^\prime) - 2 \times OPT_A(x) \ge cost_B(y^\prime) $
$(cost_A(y) - OPT_A(x)) \times 2 \ge cost_B(y^\prime) - OPT_B(x^\prime)$
$|cost_A(y) - OPT_A(x)| = O(|cost_B(y^\prime) - OPT_B(x^\prime)|)$ $\blacksquare$

Proof of Theorem 10.22.6. MaxCut 문제는 APX-hard이기 때문에 $P \neq NP$ 가정에 의해 PTAS에 속하지 않는다. MaxCut 문제는 $0.878$-approximation이 존재하는데, $0.5$ approximation이 더 간단하기 때문에 여기서는 이를 소개한다: 각 정점이 속할 bipartition을 단순히 coin flip으로 랜덤하게 결정하면, 최적해의 간선이 해당 bipartition의 비용에 기여할 확률이 $0.5$ 이다. 기댓값의 선형성에 의해, 이러한 랜덤 시행을 여러번 해보면 $0.5OPT$ 이상의 답을 얻을 수 있다. 고로 $\text{MAX-CUT} \in \text{APX}$ 이다.

Bonus: APX-Intermediate, Log-APX Completeness, Poly-APX-Complete, EXPTIME-APX-Complete...

위의 단락에서 이렇게 우리는 APX-Complete에 대한 긴 논의를 마쳤다. 이 외에도 몇 가지 흥미로운 복잡도 클래스들이 있는데, 간단하게만 논의한다.

• APX-Intermediate: Vizing Theorem과 Misra-Gries algorithm에 의하여 최대 차수가 $\Delta$ 인 그래프에 대해서 $\Delta + 1$-edge-coloring 이 존재하며 이를 찾는 알고리즘 역시 존재한다. 하지만 $\Delta$-edge coloring 의 존재성 판별은 NP-Complete임이 알려져 있다. 이 문제는 물론 $\text{APX} - \text{PTAS}$ 에 속하지만, APX-Complete 인지는 아직 알려져 있지 않다. 이러한 문제들을 APX-Intermediate 라고 한다. 다른 예시로는 Max degree minimization spanning tree ($\text{OPT} + 1$ approx), Bin packing ($\text{OPT} + O(\log (\text{OPT}) \log \log (\text{OPT})))$ 등이 있다.
• Log-APX-Complete: Dominating Set에서 $L$-reduction 되면서 Log-APX 에 속하는 문제들을 Log-APX-Complete 하다고 한다. Set Cover, Node-Weighted Steiner Tree 등이 이 부류에 속한다.
• Poly-APX-Complete: Log-APX 와 동일하게 정의되며, 최대 클리크와 최대 독립집합이 이 분류에 속한다. 위에서 보인 최대 독립집합은 bounded degree를 가정했음을 상기하라.
• EXPTIME-APX-Complete 라는 클래스도 있다. TSP가 이 경우에 속하는데, 간선의 가중치가 입력 크기에 지수적일 수 있기 때문에 이 분류에 속한다.