2018 년 9 월 10 일월요일 삼성소프트웨어멤버쉽구재현 (koosaga.com) Contents 1 소개 1 2 Length-bounded Vertex-Cut Problem 2 2.1 Definition, and Factor L 1 Approximation.............. 2 2.2 Factor L Approximation........................ 2 4 2.3 Special Case : L 4........................... 5 2.4 n factor Approximation........................ 6 3 References 6
1 소개 잘 알려진 그래프의 최소 컷 문제는, 시작 정점 s와 도착 정점 t가 있을 때 s t 경로가 없게 하기 위해서 최소 몇개의 s, t가 아닌 정점, 혹은 간선을 제거해야 하는가에 대한 문제이다. 최소 컷 문제는 그래프의 연결성과 관련된 가장 기초적인 최적화 문제이고, 다양한 최적화 문제를 최소 컷 문제로 환원할 수 있다는 점에서 그 가치가 크다. 최소 컷 문제와, 최소 컷을 사용해서 해결할 수 있는 다양한 문제의 예시를 2018년 3월 그래프의 최소 컷에 대하여 에서 다룬 바가 있다.[1] 연결성에 대한 최적화 관점에서 볼 때, 최소 컷 문제는 그래프의 연결성을 완전히 제거할 수 있는 최소 크기의 정점/간선 집합을 찾는 문제이다. 이에 대한 자연스러운 일반화 는, 그래프의 연결성을 제거하는 대신 그래프의 최단 경로 길이를 최대한 늘리는 정점/ 간선 집합을 찾는 문제이다.[2] 예를 들어, 전쟁 상황에서 두 도시를 잇는 철도망을 폭격 한다고 하자. 이상적인 경우 두 도시의 연결성을 아예 끊어버리는 것이 좋겠으나 (최소 컷), 전부 끊기에는 비용이 너무 큰 경우가 생길 수 있다. 이러한 경우 더 실용적인 대안 은, 두 도시를 통과하는 최단 시간이 1일을 초과하게 되도록 철도망을 폭격하는 것이다. 이에 우리는 L-length bounded (s, t) cut을 정의한다. L-length bounded (s, t) vertex cut은, s, t를 포함하지 않는 정점들의 부분집 합으로, 이 정점들을 제거했을 때 s 에서 t로 가는 최단 경로가 L 초과이다. L-length bounded (s, t) edge cut은 간선들의 부분집합으로, 이 간선들을 제거했을 때 s에서 t로 가는 최단 경로가 L 초과이다. 그래프의 최소 컷은 Maximum Flow Minimum Cut Theorem[3]을 사용해서 다항 시간 에 구할 수 있으나, 최소 L-length bounded cut은, 간선/정점을 막론하고 NP-Complete 문제로 다항 시간 풀이가 존재하지 않는다.[4] 고로 우리는 문제 해결의 주안점을 달 리 두기로 한다. 우리는 특정한 제약 조건 내에서 문제를 효율적으로 해결하는 방법이 존재하는지, 또는 문제를 해결하는 근사 알고리즘 (approximation algorithm)이 존재 하는지의 여부를 다룬다.
근사 알고리즘이라 함은, 문제에 대한 최적해 를 제공하지는 못하나, 문제에 대한 최 적해에 근접한 해(근사해)를 빠른 시간에 찾는 알고리즘이다. 일반적으로 근사 알고 리즘을 평가하는 주된 기준은, 최적해에 비해서 근사해의 비효율성의 비율이 최대 얼마인가? 를 계산하고, 이 최대 비효율성이 낮은 알고리즘을 좋은 근사 알고리즘 이라고 평가한다. 이 문제에서 효율성 은 결국 끊어야 하는 집합의 크기로 판단될 것이고, 최적해에 비해서 비효율성의 비율이 X 이하라는 것은, 최적해의 크기가 만약 OP T 라면, 우리가 근사 알고리즘을 썼을 때 항상 X OP T 이하 크기의 해를 얻음이 보장된다는 것을 뜻한다. 이를 Factor X Approximation 이라 부른다. [5] 2 2.1 Length-bounded Vertex-Cut Problem Definition, and Factor L 1 Approximation Length-bounded cut이 Minimum Cut의 일반화라면, 근사 알고리즘 역시 다항 시간 Minimum Cut 알고리즘에 기반하여서 시작하는 것이 좋을 것이다. 다항 시간 Minimum Cut은 Max-Flow Min-Cut Theorem을 사용하여 구할 수 있고, 이의 내용은 다음과 같 다. Definition 1. 그래프 와 두 정점 s 6= t에 대해서, s t 정점 독립 경로 집합 은 s 에서 시작하여 t에서 끝나는 경로들의 집합으로, 집합 상에 있는 임의의 서로 다른 두 경로에 대해서, 두 경로가 공유하는 정점이 s, t 외에는 없는 집합이다. 이 집합의 최대 크기를 A (s, t) 라 하고, 의 Minimum Cut의 크기를 V (s, t) 라고 하자. Theorem 1. 그래프 와 두 인접하지 않은 정점 s, t에 대해서, 의 Minimum Cut의 크기 V (s, t) 는 상에서 s, t를 잇는 정점 독립 경로 집합의 최대 크기 A (s, t) 와 같다. Remark. Theorem 1은 정확히 Max-Flow Min-Cut Theorem이 아니며, 실제 이름은 Menger s Theorem이다.[6] Menger s Theorem은 Max-Flow Min-Cut Theorem을 사용 하여 쉽게 증명되며, 그 발견 시기도 훨씬 이르다. 이 글에서는 Menger s Theorem을 사용함이 더 의미 전달에 명확하고, 이보다 더 많은 내용이 필요하지 않기 때문에 이를 사용한다.
이 Theorem을 Length-bounded Cut으로 일반화할 수 있을까? 일단 단순히 일반화된 명제를 제시하는 것에서부터 시작해 보자. Definition 2. 그래프 와 두 정점 s 6= t에 대해서, s t 정점 독립 L-경로 집합 은 s 에서 시작하여 t에서 끝나는 길이 L 이하의 경로들의 집합으로, 집합 상에 있는 임의의 서로 다른 두 경로에 대해서, 두 경로가 공유하는 정점이 s, t 외에는 없는 집합이다. 이 집합의 최대 크기를 A L (s, t) 라 하고, 의 L-length bounded minimum cut의 크기를 VL (s, t) 라고 하자. Remark. s t 정점 독립 L-경로 집합의 최대 크기는 MCMF (Successive Shortest Path) 알고리즘을 사용하여서 다항 시간에 구할 수 있다. Proposition 1. 그래프 와 두 인접하지 않은 정점 s, t에 대해서, 의 L-Length bounded Cut의 크기 VL (s, t) 는 상에서 s, t를 잇는 정점 독립 L-경로 집합의 최대 크기 A L (s, t) 와 같다. 만약 명제 1이 맞다면, NP-Complete 문제인 L-length bounded cut의 크기를 다항 시간 안에 구할 수 있으니, P = N P 이다. 고로 위 명제가 성립할 것이라는 우리의 기대는 헛된 기대일 가능성이 높으며, 실제로도 아래와 같은 반례가 존재한다. Figure 1. L = 5일 때, u, v를 잇는 정점 독립 L-경로 집합의 최대 크기는 1이나, 끊어야 하는 정점의 개수는 2개이다. 반례를 찾음으로써 명제 1이 틀림은 확실해졌지만, 아직도 희망은 있다. 이 단락의 최 종적인 목표는 최적해를 찾는 것이 아니라, 근사 알고리즘을 찾는 것이기 때문이다. 다 행이 우리는 위 결론을 통해서, 이 문제를 해결하는 간단한 L 1 factor approximation 알고리즘을 찾을 수 있다. Lemma 1. VL (s, t) A L (s, t) (증명은 자명하여 생략.) Theorem 2. L-length bounded cut은 L 1 factor approximation이 존재한다.
Proof. 알고리즘은 다항 시간에 s, t를 잇는 최대 크기 정점 독립 L-경로 집합을 찾은 후, 이 집합에 속하는 모든 정점들을 제거해 주는 방법이다. 이 방법으로 정점을 제거해 주면 이후 s, t를 잇는 최단 경로의 크기는 L을 초과할 수 밖에 없다 (그렇지 않다면 최 대라는 가정에 모순이다.) 이 과정에서 제거되는 정점의 개수는 최대 (L 1) A L (s, t) 인데, VL (s, t) A L (s, t) 임은 자명하니, (L 1) AL (s, t) (L 1) VL (s, t) = (L 1) OP T 라는 결론이 나온다. Factor b L2 c Approximation 2.2 이제 조금 더 나은 Factor를 찾아보자. 첫 시작점은 L 로, 2 앞서 찾은 L 1 Factor와 Big-O notation 상에서는 같으나, 자명하지 않은 방법들을 사용한다. 접근 방법은 현재 최단 경로의 길이에 따라서 케이스를 나누는 것이다. 현재의 L 1 factor 알고리즘은 최단 경로가 작을 수록 제거하는 정점의 개수가 작은 경향성을 보인다. 한편, 최단 경 로가 충분히 크다면 최단 경로들에 대한 컷을 순서대로 막아나가는 방법을 사용할 수 있다. L 2 factor approximation을 하기 위해서는, 최단 경로가 작을 때는 첫 번째 성질을, 클 때는 두 번째 성질을 활용하면서 집합을 찾는다. Theorem 3. 모든 그래프 와 인접하지 않은 두 정점 u, v V ()와 자연수 n 2에 대해서, 1 V A n d(s, t) + 1. Proof. m = n d(s, t) + 1 이라 하자. m에 대한 수학적 귀납법을 사용한다. 기저 조건 (m = 1) : 에서 s t를 잇는 임의의 최단 경로에 속하는 모든 간선들을 모아 0 을 만들자 (최단 경로 DA). 0 의 모든 경로의 길이는 항상 d(s, t) = n 이다. 고로 0 의 minimum cut은 minimum n-length bounded cut이 되고, 0 의 최대 정점 독립 집합은 정점 n-경로 독립 집합이다. 고로, Theorem 1에 의하여, V A = 1이다. 귀납 조건 (m > 1) : 앞서와 같이 0 을 만들자. 0 의 모든 경로의 길이는 항상 d(s, t) 이다. 고로 0 의 임의의 minimum d(s, t)-length bounded cut X를 구할 수 있으며, Theorem 1에 의해서 X = Vd(s,t) (s, t) = A d(s,t) (s, t)이다. 에서 X에 속한 정점을 제거할 경우, d\x (s, t) > d (s, t) 가 성립한다. 만약 d\x (s, t) > n일 경우 자명하니, 아님을 가정하자. 이 때는 귀납 가정에 의하여
1 \X Vn (s,t) \X A m d\x (s, t) + 1 m d (s, t) 가 성립한다. \X 수식 전개시, An \X Vn (s, t) A n (s, t), X = Ad(s,t) (s, t) An (s, t), Vn (s, t) \X (s, t) + X Vn (s, t) + A n (s, t) 이니, 이를 합치면 1 V A m d (s, t) + 1 가 성립한다. Theorem 4. 모든 그래프 와 인접하지 않은 두 정점 u, v V ()와 자연수 n 2와 인접하지 않은 두 정점 s, t에 대해서, 1 V A b n2 c. Proof. 만약, d(s, t) n/2 + 1 일 경우, Theorem 3에 의해서 성립한다. 고로, d(s, t) (n + 1)/2 를 가정한다. 우리는 다음과 같은 적당한 d(s, t) D n를 잡아서, 다음을 수행한다. 1. s t간 최단 경로가 D 이하일 때까지, 임의의 s t 최단경로를 찾고, 최단 경로 상에 속하는 모든 정점 (s, t 제외) 을 제거한다. 제거한 정점 집합을 X라 한다. \X 2. \ X에서 Theorem 3을 사용해서 (n D) An (s, t) 크기의 정점 집합 Y 을 찾는다. 3. X Y 를 반환한다. \X 첫번째 단계에서 제거한 최단 경로의 개수를 r 이라 하자. 이 때, An (s, t) A n (s, t) d, X r(d 1), Y (n D)(A n (s, t) r) 을 만족한다. 고로 Vn (s, t) X + Y r(d 1) + (n D)(A n (s, t) r) 이다. 이 때 D = b(n + 1)/2c 로 두면, Vn (s, t) bn/2ca n (s, t) 가 된다. 3 References 1. 삼성전자 소프트웨어 멤버쉽 2018년 3월 개인 과제. 2. Lova sz, La szlo, Vı ctor Neumann-Lara, and Michael Plummer. Mengerian theorems for paths of bounded length. Periodica Mathematica Hungarica 9.4 (1978): 269-276. APA 3. Wikipedia, Max-flow Min-cut Theorem https://en.wikipedia.org/wiki/
Max-flow_min-cut_theorem 4. Baier, eorg, et al. Length-bounded cuts and flows. International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg, 2006. 5. Wikipedia, Approximation Algorithms, https://en.wikipedia.org/wiki/ Approximation_algorithm 6. Wikipedia, Menger s Theorem, https://en.wikipedia.org/wiki/menger% 27s_theorem