Balanced Cut

2020-1학기, 대학에서 ‘알고리즘’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

---

Definition. Cut

A set of edges whose removal leaves a graph disconnected.

포스트를 앞에서부터 천천히 따라왔다면, Network Flow 챕터에서 Network Flow 문제가 Minimum Cut Problem과 dual problem 관계임을 공부했을 것이다.

Problem. Minimum Cut Problem

Given a graph and a budget $b$, find a cut with at most $b$ edges.

* search problem의 형태로 기술 되었다.

이 문제는 Network Flow 알고리즘으로 정말 쉽게 풀 수 있다.

• 각 edge에 1의 capacity를 할당
• source 노드 $s$를 정한다.
• 나머지 $n-1$개 노드에 대해 그들은 sink 노드 $t$로 설정해 $n-1$번 Network Flow 알고리즘을 돌린다.
• 그 중 가장 적은 비용의 cut을 minimum cut으로 삼는다.

그러나 이렇게 쉬운 형태라면 NP에 등장할 수 없다. Balanced Cut 문제는 분할하는 두 그래프의 균형이 맞아야 한다.

Problem. Balanced Cut Problem

Given a graph with $n$ vertices and a budget $b$, find a cut $(A, B)$ such that $\left| A \right|, \left| B \right| \ge n/3$ and at most $b$ edges in the cut.

* search problem의 형태로 기술 되었다.

즉, 비용 $b$를 맞추면서 분할된 그래프 $A$, $B$의 크기가 비슷해야 하는 것이다! Balanced Cut Problem은 Minimum Cut Problem과 달리 poly-time algorithm이 존재하지 않는다.

함께보기

• Network Flow
• P and NP