Introduction
$T$-join 문제의 LP-relaxation을 생각해보자. (이 문제의 정의는 필자의 이전 글들에서 여러번 언급 했으므로 자세한 설명은 생략한다.)
\[\begin{align*} \text{minimize:} & & \sum_{e \in E} c_e \cdot x_e && \\ \text{subject to:} & & x(\delta(S)) \ge 1 & &\forall S \subseteq V, \lvert S \cap T \rvert \equiv 1\pmod2 \\ & & x_e \ge 0 & & \forall e \in E \end{align*}\]이 문제의 경우, LP의 optimal solution이 integral 하여, LP를 해결하면 원본 문제를 효율적으로 (다항 시간에) 해결할 수 있다. 하지만, 이 주장에는 숨겨진 부분이 있다. LP의 constraint의 수가 exponentially 많기 때문에, 다항 시간에 해결하는 것이 비자명 하다는 것이다.
LP를 ellipsoid method를 이용하여 해결한다 하면, separation oracle이 있어야 한다. 참고로, separation oracle이라 함은, LP polytope 안에 들어오지 않는 벡터가 주어졌을 때, violate 하는 constraint를 (다항 시간에) 알려주는 알고리즘을 의미한다.
하지만, 이 separation oracle의 존재를 많은 사람들이 알고 사용하는 것에 비해, 정확히 어떻게 구성하는지 잘 알지 못하는 사람도 않은 것 같다. 이 글에서는 이 문제의 separation oracle을 효율적으로 구하는 데에 활용될 수 있는 문제 및 해당 문제의 효율적인 알고리즘을 알아본다. Gomory-Hu Tree 에 대한 글의 앞부분을 미리 읽어보는게 유용할 수 있을 것이다.
Problem Definition
유한 개의 정점을 가지는 무향 그래프 $G = (V, E)$ 와 간선에 대한 가중치 함수 $c : E \to \mathbb{Q}_{\ge 0}$ 가 주어졌다고 하자.
그리고 짝수 크기의 정점 부분집합 $T$ 가 주어졌다고 하자. (편의상, $T$는 공집합이 아닌 경우를 고려하자.)
Odd minimum cut 문제는 $W \subseteq V$, $\lvert W \cap T \rvert \equiv 1 \pmod 2$ 를 만족하는 $W$ 가운데, $c(\delta(W))$ 가 최소인 것을 구하는 문제이다. 참고로, $X \subseteq E$ 에 대해 $c(X) = \sum_{e \in X} c_e$ 를 나타내며, 문제 이름의 단어 “odd”는 $T$ 와 intersection의 기우성을 나타낸다.
Observation
이 문제의 성질에 대해 관찰해보자.
$G$ 의 minimum cut (중 하나) $(M, \bar M)$ 을 구했다고 가정해보자. 만약, $\newcommand{\odd}[1]{\lvert #1 \cap T \rvert \equiv 1 \pmod 2} \newcommand{\even}[1]{\lvert #1 \cap T \rvert \equiv 0 \pmod 2} \odd M$ 라면, 문제의 답을 찾은 것이 될 것이다. 하지만, 그렇지 않다면, 어떤 정보를 얻을 수 있을까?
Lemma. $(M, \bar M)$ 이 $G$ 의 minimum cut 이라 하자. 그러면, minimum odd cut $(X, \bar X)$ 가 존재해, $X \subseteq M$ 이거나, $X \subseteq \bar M$ 이다.
Proof.
-
만약, $M$이 odd 라면 명백하니, $M$이 even이라 가정하자.
-
Minimum-cost odd cut $Y$를 잡자.
-
기우성에 의해 $Y \cap M$ 과 $Y \cap \bar M$ 중 하나는 odd 이므로, WLOG, $Y \cap M$ 이 odd라 가정하자.
-
만약, $Y \cap \bar M$ 이 공집합이라면, 증명이 끝나고, $\bar M \cap \bar Y$ 가 공집합이어도, $\bar Y \subseteq M$ 이므로 증명이 끝난다.
-
고로, $Y \cap \bar M$ 이 공집합이 아님을 가정할 수 있고, 그러면 cut function의 성질과 $c(\delta(M))$의 minimality에 의해 \(\begin{align*}c(\delta(M)) + c(\delta (Y)) &\ge c(\delta(M \cap Y) + c(\delta(M \cup Y))) \\ &\ge c(\delta(M \cap Y)) + c(\delta(M)) \end{align*}\) 이 되므로, $M \cap Y$ 가 $M$의 subset 인 minimum odd cut이 됨을 알 수 있다. $\square$
이 Lemma를 기반으로 $M$이 even cut인 상황에 대해 생각해보면, $M$을 하나의 정점으로 contract 한 그래프 $G_1$과 $\bar M$ 을 하나의 정점으로 contract한 그래프 $G_2$ 가 있을 때, $G_1$의 minimum $(T \cap V(G_1))$-odd cut과 $G_2$의 minimum $(T \cap V(G_2))$-odd cut 중 하나가 문제의 답이 됨을 알 수 있다. (참고로, $T$ 집합은 항상 짝수여야 하므로, contraction의 결과로 새로 만들어진 정점은 $T$ 정점으로 간주하지 않는다.)
Observation. $\even M$ 일 때, $G_1 := G / M$, $G_2 := G/\bar M$ 으로 잡고, $T_1 := V(G_1) \cap T$, $T_2 := V(G_2) \cap T$ 라 하자. $G$에서의 minimum $T$-odd cut의 cost $C$와 $G_1$ 에서의 minimum $T_1$-odd cut의 cost $C_1$, $G_2$ 에서의 minimum $T_2$-odd cut 의 cost $C_2$ 간에는 $C = \min(C_1, C_2)$ 의 관계가 성립한다.
Algorithm
위의 관찰을 기반으로, 다음의 알고리즘을 생각해볼 수 있다.
- Cut tree $G_T := (N, F)$ 을 모든 $T$의 원소의 쌍에 Gomory-Hu algorithm을 적용해 construct 한다.
- 이 때, $N$의 원소는 1개 이상의 정점으로 구성된 집합일 것이다.
- solve($G_T = (N, F)$, $T$)
- weight가 최소인 edge $f^\star$ 를 잡고, $f^\star$ 로 $N$이 partition 되는 두 정점 집합을 $N_1, N_2$라 하자.
- $\odd{N_1}$ 이라면, $N_1$ 을 반환한다.
- 아니라면, output minimum one among solve $(G_T[N_1], T \cap N_1)$ and solve $(G_T[N_2], T \cap N_2)$.
Analysis.
- 이 알고리즘은 매번 보는 정점 집합의 크기가 줄어드므로, solve 함수가 유한 시간 안에 terminate 할 뿐만 아니라, 다항 시간에 동작함 까지 명백하다.
- 그리고, Gomory-Hu tree의 성질을 고려해보면, subtree만 매번 살펴봐도 앞선 섹션의 observation의 작업을 동등하게 수행한다는 점 또한 알 수 있다. $\square$
Application
이 알고리즘을 활용하면, minimum odd cut의 크기가 1 이상인지/미만인지를 검사하는 형태로 다항 시간에 동작하는 $T$-join 문제에 대한 separation oracle을 구현할 수 있다.
Reference
https://www.jstor.org/stable/3689360?seq=1