Simple Cubic General Maximum Matching Algorithm

General Maximum Matching Algorithm에 대해 삽질을 많이 했고, 다른 사람이 삽질을 하지 않기 위해서 이 글을 쓰려고 합니다.

이 글은 매칭에 대해 잘 이해를 하고 있다고 가정하고, 이분그래프의 매칭을 찾는 법을 아는 사람을 위한 글입니다.

이분그래프에 대해서는 O(EV^0.5) 풀이가 존재하고, 시간복잡도 증명이 어렵지만 그 부분을 제외하고는 이해할 만 합니다. 

사실 일반그래프에 대해서도 마찬가지가 존재하나, 구현하기가 굉장히 어렵습니다. 그래서 O(V^3) 시간 알고리즘을 소개하려고 합니다.

먼저 General Graph의 Matching에 어려움의 대해 설명을 하겠습니다.

odd는 정점에서 간선을 홀수 번 타고 갈 수 있는 점, even은 정점에서 간선을 짝수번 타고 갈 수 있는 점이라고 말하겠습니다.

Graph 에서 Augment Path를 찾을 때, 이분그래프는 2가지 색으로 잘 칠해질 수 있기 때문에(odd, even) odd 정점이 비어있는지 아닌지만 확인하면 됩니다.

하지만 General graph에서는 어떤 정점이 odd이면서 동시에 even일 수 있기 때문에, 잘 처리를 해야 하고 처리를 한다고 해도 역추적이 어렵습니다.

우리는 이 Augment Odd cycle을 Blossom이라고 부르겠습니다.

이 cycle에는 특징이 하나 있습니다. 모든 Cycle위에 있는 점은 even입니다. 방향에 따라서 case가 2개가 나뉘게 되는데, 두 케이스 모두 blossom 위를 한 방향이나 반대방향으로 돌면서 Augment Path를 만들게 됩니다.

그래서 우리는, 이 blossom 위에 있는 점을 모두 even이라고 표시 해 줄것입니다. 이렇게 되면, augmenting path를 탐색하지 못하는 일이 없고 이것은 Edmond의 논문에서 증명이 되어 있습니다. 그러면 역추적을 할 때 굉장히 힘들것입니다. 우리는 이 역추적을 하는 방법을, blossom을 줄이지 않고 두개로 확장하는 방법을 사용할 것 입니다.

그림을 보면 10 - 3 - 4 - 6 - 5 의 blossom 이, 10 - 3 - 4 - 6 - 5와 10 - 5 - 6 - 4 - 3으로 나뉘어져 있다는 것을 확인할 수 있습니다. 우리는 탐색을 even인 점에서만 시작하기 때문에 (odd인 점은 단지 matching을 타고 가는것으로 끝납니다.) 탐색을 중복해서 하는일은 없게 되고, 10 - 3 - 4 - 6 - 5 가 모두 10에서 시작하는 blossom에 속해있다. 라는 사실을 저장해 두면, 다른 blossom이 생겼을 때 합치는 일도 어렵지 않습니다.

제가 과제로 작성했던 pdf 하나를 첨부하고 글을 마치도록 하겠습니다. 소스코드는 제가 첨부한 pdf안에 존재합니다.

201805.pdf

참고 문헌:

Maximales matching in Graphen [Pape & Conradt 1980]

Data Structures and Network Algorithms [Tarjan 1987]

추가:

이 방식의 시간복잡도가 O(V^3)이지만, 대부분의 경우에 O(VE)정도로 도는것 같습니다. 증명 혹은 반증은 하지 못했는데 나중에 O(VE^0.5) 알고리즘에 대해 공부하면서 써보려고 합니다. 

추가 2: 트리를 나누어서 방문한 모든 odd, even 정점을 기억하는게 아니라 아니라, 그냥 even인 점을 타고가기만 하는 경우에는 반례가 있습니다.