독립 집합에 관한 노트

작년 말부터 올해 초까지 있었던 일입니다. 학교 동료한테서 소개 받은 문제를 고민하던 차에 굉장한 아이디어가 떠올라서 그 문제를 뚝딱 풀어버렸습니다. 너무 기쁜 나머지 문제를 소개해 준 동료는 물론 지도 교수님을 포함한 여러 사람들에게 이 사실을 널리 알리고 다녔죠. 주변 사람들도 그럴듯하다며 인정해 주었습니다. 며칠이 지났을까, 불현듯 그 증명에서 가장 핵심적인 단계가 참이 아닐 수도 있겠다는 의구심이 들었고, 조금 고민해 보니 정말 틀렸더군요. 한동안 주위 사람들에게 제 증명이 사실은 틀렸다고 말하고 다니느라 멋쩍은 시간을 보냈습니다.

 

이렇게 언뜻 보기에는 참일 것 같은 명제에 반례를 발견하게 되면 개인적으로 이를 블로그에 정리합니다. 스스로를 위한 비망록이면서도 혹 누군가가 비슷한 고민을 할 때 소소한 참고자료로서도 활용될 수 있을 것으로 생각하기 때문입니다.

---

어떤 그래프 \(G = (V, E)\)가 주어질 때, 독립 집합(independent set)은 서로 인접하지 않은 정점의 집합을 의미합니다. 다시 말해, 어떤 \(I \subseteq V\)에 대해, \(I\)에 속한 임의의 서로 다른 두 정점 \(u, v \in I\)를 잇는 간선 \((u, v)\)가 \(E\)에 존재하지 않을 때, 우리는 \(I\)를 독립 집합이라고 부릅니다. 아무 정점도 뽑지 않거나, 하나의 정점만 뽑은 경우도 독립 집합의 정의에 부합하므로, 우리는 대개 크기가 가장 큰 독립 집합을 찾는 것을 목표로 합니다.

 

독립 집합과 큰 연관이 있는 개념이 있습니다. 바로 정점 덮개(vertex cover)인데요. 이는 그래프의 모든 간선 \(E\)를 "덮는" 정점의 집합을 의미합니다. 더 자세히 말하자면, 어떤 \(C \subseteq V\)에 대해, 임의의 간선 \((u, v) \in E\)에 대해 \(u\)나 \(v\) 중 적어도 하나가 \(C\)에 속한다면, 우리는 \(C\)를 정점 덮개라고 부릅니다. 모든 정점을 뽑은 경우도 가능한 정점 덮개에 해당하므로, 많은 경우 우리는 크기가 가장 작은 정점 덮개를 찾고자 합니다.

 

독립 집합과 정점 덮개가 큰 연관이 있는 이유는 바로 서로 보완적인 관계에 있기 때문입니다.

정리 1. 독립 집합과 정점 덮개의 보완성

---

어떤 그래프 \(G = (V, E)\)에 대해, \(I \subseteq V\)가 독립 집합이라면, \(V \setminus I\)는 정점 덮개이다. 반대로, \(C \subseteq V\)가 정점 덮개라면, \(V \setminus C\)는 독립 집합이다.

증명은 너무 유명해서 생략합니다. 잘 모르신다면, 한번 고민해 보셔도 좋겠습니다. 정리 1을 통해서 쉽게 유추할 수 있는 사실은, 만약 어떤 그래프 \(G = (V, E)\)에서 독립 집합의 최대 크기가 \(|V|/2\)를 넘지 못한다면, 그 그래프에서 정점 덮개의 최소 크기는 적어도 \(|V| / 2\)라는 것입니다.

 

이제 제가 잘못 생각한 명제를 소개할 차례입니다. 어떤 그래프 \(G = (V, E)\)에 대해, 그것의 여그래프(complement graph)를 \(\overline{G} = (V, \overline{E})\)라고 하겠습니다. 다시 말해, \(\overline{G}\)는 \(G\)와 동일한 정점 집합을 갖지만, 임의의 정점 \(u, v \in V\)에 대해, \(u\)와 \(v\)가 \(\overline{G}\)에서 인접할(즉, \((u, v) \in \overline{E}\)) 필요충분조건은 두 정점이 \(G\)에서는 인접하지 않은(즉, \((u, v) \not\in E\)) 것입니다. 저는 다음과 같은 가설을 세웠습니다.

어떤 그래프 \(G = (V,E)\)에서의 독립 집합의 최대 크기가 \(|V| / 2\)를 넘지 못한다면, 그것의 여그래프 \(\overline{G}\)에서의 독립 집합의 최대 크기는 적어도 \(|V| / 2\)이다.

 

나름 위와 같은 가설을 세운 이유는 있습니다. 앞에서 원래 그래프에서의 독립 집합의 최대 크기가 \(|V|/2\)를 넘지 못하면 분명 정점 덮개의 최소 크기는 적어도 \(|V|/2\)라고 하였습니다. 그러고는 원래 그래프에서의 최소 정점 덮개가 왠지 여그래프에서의 독립 집합이 될 것 같았습니다. 따라서 위 명제가 참이라고 결론을 지었었죠. 네, 이는 완벽히 잘못된 말입니다. 최소 정점 덮개의 두 정점 사이에 반드시 간선이 있으리라는 보장이 없기 때문이죠.

 

이 생각에 도달한 후, 결국 저는 아래를 보일 수 있었습니다.

정리 2. 원래와 여그래프 모두에서 작은 최대 독립 집합을 갖는 그래프

---

임의의 자연수 \(k\)에 대해, \(G_k\)와 \(\overline{G_k}\) 모두 독립 집합의 최대 크기가 \(|V|/k\)를 넘지 않는 그래프 \(G_k\)가 존재한다.

[증명] 각각 \(k\) 개의 정점씩으로 구성된 완벽 \(k\)-분할 그래프(complete k-partite graph)를 \(G_k = (V, E)\)로 두겠습니다. 즉, \(V\)는 \(|V_1| = |V_2| = \cdots = |V_k| = k\)을 만족하는 \(V_1, V_2, \cdots, V_k\)의 합집합 \(V := V_1 \cup V_2 \cup \cdots \cup V_k\)이고, 각 \(i = 1, 2, \ldots, k\)에 대해, \(V_i\)의 한 정점 \(u\)는 \(V_i\)를 뺀 모든 정점 \(v \in \bigcup_{j \neq i} V_j\)과 인접한 그래프를 말합니다. 정점의 개수 \(|V|\)가 \(k^2\) 개임을 확인하시기 바랍니다.

 

그러면 \(\overline{G_k}\)는 어떻게 생겼을까요? \(G_k\)에서 각 \(V_i\)의 정점 사이에만 간선이 존재하지 않았으므로, \(\overline{G_k}\)는 각 \(V_i\)가 완벽히 연결된, 즉 \(k\) 개의 \(k\)-클릭(clique)으로 이루어진 그래프임을 알 수 있습니다.

그림 1. (ㄱ) \(G_3\)의 도식. (ㄴ) \(\overline{G_3}\)의 도식.

이제 \(G_k\)와 \(\overline{G_k}\) 각각에서 최대 독립 집합을 구해 봅시다. 먼저 \(G_k\)에서 어떤 \(V_i\)의 한 정점 \(v \in V_i\)가 최대 독립 집합 \(I\)에 뽑혔다고 해 보겠습니다. 그러면 \(V_i\)를 제외한 나머지 모든 부분 \(\bigcup_{j \neq i} V_j\)의 정점들은 \(v\) 때문에 \(I\)에 뽑힐 수 없습니다. 따라서 \(I\)는 \(V_i\)의 모든 정점을 넣는 것밖에는 방법이 없으며 따라서 \(|I| = k = |V|/k\)를 만족합니다.

 

반대로 \(\overline{G_k}\)에서는 각 \(V_i\)가 완벽히 연결되어 있으므로 \(\overline{G_k}\)의 최대 독립 집합 \(\overline{I}\)에는 각 \(V_i\)에서 최대 하나의 정점만이 참여할 수 있습니다. 총 \(k\)개로 분할되어 있으므로, 여전히 \(| \overline{I} | = k = |V|/k\)를 만족합니다. □

---

요새 바쁘게 지내고 있습니다. 비록 이 반례 때문에 연말연시에 고민했던 그 문제에는 현재 별다른 진전이 없지만, 다른 문제들에서 이런저런 성과들을 얻고 있습니다. 그 때문에 블로그에 포스팅하고 싶은 주제가 문득문득 생겨도 이를 쓰지 못하고 그저 묵혀만 두고 있는데요. 나중에 숨을 좀 고를 때가 오면 그때 이것저것 정리해 보도록 하겠습니다.

 

고맙습니다.