독립 집합에 관한 노트

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

 

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

---

어떤 그래프 $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)를 $\bar{G}=(V,\bar{E})$라고 하겠습니다. 다시 말해, $\bar{G}$는 $G$와 동일한 정점 집합을 갖지만, 임의의 정점 $u,v\in V$에 대해, $u$와 $v$가 $\bar{G}$에서 인접할(즉, $(u,v)\in \bar{E}$) 필요충분조건은 두 정점이 $G$에서는 인접하지 않은(즉, $(u,v)\notin E$) 것입니다. 저는 다음과 같은 가설을 세웠습니다.

어떤 그래프 $G=(V,E)$에서의 독립 집합의 최대 크기가 $|V|/2$를 넘지 못한다면, 그것의 여그래프 $\bar{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,\dots ,k$에 대해, $V_i$의 한 정점 $u$는 $V_i$를 뺀 모든 정점 $v\in \bigcup _{j\ne 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\ne i}{V}_j$의 정점들은 $v$ 때문에 $I$에 뽑힐 수 없습니다. 따라서 $I$는 $V_i$의 모든 정점을 넣는 것밖에는 방법이 없으며 따라서 $|I|=k=|V|/k$를 만족합니다.

 

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

---

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

 

고맙습니다.