유량 관련 알고리즘 정리

[2015/07/24 MCMF 보강]

[2016/10/03. 옛날에 썼던 글이라 내용을 대폭 보강해서 다시 올린다. 이 글은 "정리하는" 개념의 글이니, 문제나 알고리즘에 대한 구체적인 설명은 따로 찾길 바란다.]

[2016/10/14 잡설을 추리고 증명 관련 부분을 개별 글로 뺐다. 증명 뿐만 아니라 "답을 출력하는" 일이 필요하다면 해당 글 참고] 

유량(flow) 관련 문제는 대부분 유량을 흘릴 수 있는 경로를 찾고 그 경로에 유량을 보내줌으로써 해결한다.
비슷비슷해서 난 별로 차이가 없는 줄 알았는데 얼마전 DFS로 maxflow의 증가경로를 찾으면 안된다는 얘기를 듣고 멘붕함. 이 기회를 통해서 정리하려 한다.

여담으로, 프로그래밍 콘테스트 챌린징의 네트워크 유량 부분에 굉장히 중요하고 쉽게 배우기 힘든 유형들이 많이 정리되어 있다. 이 글은 알고리즘 정리에 초점이 맞춰져 있으니, 모델링 유형에 대해서는 그 책을 꼭 참고하기 바란다.

[Maximum Flow]

1. 그래프에서 source에서 sink로 흐를 수 있는 최대 유량, Maximum Flow를 찾는 문제이다.

2. 기본적인 알고리즘은, 증가 경로를 "어떻게든" 찾은 후 그 쪽으로 flow를 보내주는 방식으로 해결한다. 탐욕법의 일종이다. 이를 Ford-Fulkerson Algorithm이라고 한다. Ford-Fulkerson Algorithm은 증가 경로를 구체적으로 어떻게 찾는지 명시하지 않았다. 지수적인 방법으로 찾아도 포드 풀커슨이고 고로 이걸 Ford-Fulkerson Method로 불러야 한다는 의견도 존재한다. 다행이 우리는 BFS나 DFS를 아니까 둘 중 하나를 쓰면 된다.

3. DFS든, BFS든 기본적으로 시간 복잡도는 O(f * E) 이다. f는 유량의 총 크기로 만약 크기가 확실치 않다면 다항시간에 풀 수 없는 것이나 마찬가지다.

4. 하지만 BFS를 사용했을때는 증가 경로를 VE번 이상 찾지 않는다는 것이 증명되었다. 증명 따라서 Maximum Flow 문제는 무조건 BFS를 사용해야 하며 시간 복잡도는 O(VE^2)이다. BFS를 쓰는 Ford-Fulkerson Algorithm을 Edmonds-Karp Algorithm이라고 부른다.

5. 이러한 아이디어에서 착안해서 Dinic's Algorithm이라는 알고리즘 역시 존재한다. Dinic's Algorithm은 최단 경로를 이룰 수 있는 간선들을 명시적으로 그래프로 만든 후, O(VE) 시간 안에 가능한 flow를 모두 흘려준다. 초기에 bfs로 최단 경로를 이룰 수 있는 그래프만을 추출하고 (이를 Level Graph라고 한다), 이후 dfs로 O(E)번 증가 경로를 찾는데 찾는 과정에서 만약에 포화된 간선이 존재한다면 그 간선을 그래프에서 제거한다. 고로, 각각의 간선은 증가 경로의 일부로 작동하거나, 한번 사라져서 다시 보지 않게 된다. 증가 경로의 길이는 길어야 V이니 증가 경로의 일부로 작동하는 횟수는 VE, 삭제되는 횟수는 E이다. 고로 O(VE) 안에 해당 최단 경로에서 가능한 flow를 모두 보낸 것이다. 이것이 O(V) 번 반복되어서, 시간 복잡도는 O(V^2E)가 된다.

6. 모든 에지의 capacity가 0 혹은 1일 때 Dinic Algorithm은 O(E)에 blocking flow를 찾을 수 있다. 위 알고리즘의 작동방식을 생각해 보면 직관적으로 이해할 수 있을 것이다. 여기서 놀라운 것은, 이 때 iteration 횟수도 Min(V^(2/3), E^(1/2)) 번으로 제한된다고 한다. 증명  얼마전 이 사실로 푸는 문제가 CF에 출제됐을 때 몇명 밖에 못 풀었으니 잘 알려진 내용은 아닌듯.

7. 정리하자면, DFS로 찾으면 O(fE), BFS로 찾으면 O(min(fE, VE^2)), DFS와 BFS의 이상한 혼종 (...) 인 Dinic을 쓰면 O(min(fE, V^2E)) 에 풀 수 있다. 또한, Dinic은 unit capacity에서 min(V^(2/3) * E, E^3/2) 에서 돌아간다.

8. Maximum Flow도 유용하지만, Min-Cut Max-Flow Theorem (증명) 에 의해서 Minimum Cut을 찾는 데 쓰이거나, 이분 그래프의 최대 매칭을 찾는 데 (Bipartite Matching)도 사용된다.  Bipartite Matching은 Maximum Flow의 special case로 이후 후술한다.

9. 이상하게 PS에서는 네트워크 플로우 알고리즘을 worst case를 가지고 입력 제한을 주지 않는다. 위에 있는 알고리즘이 worst case에 도달하는 경우가 굉장히 적기 때문. 특히 문제에서 요구하는 플로우 네트워크가 special한 경우가 많기 때문에 더 그렇다. PS 할때는 V^2E를 직접 계산한다기 보다는, 에드몬드 카프 안되면 Dinic 쓰면 풀리는 문제고, Dinic 써서 안되면 그냥 플로우를 써서 애초에 못 푸는 문제.. 뭐 그런 식이다. 많은 문제를 풀면서 출제자의 눈치를 (...) 까거나, 아니면 그냥 Dinic만 쓰자.. ㅠㅠ Z축 위에 계신 것으로 유명한 어떤 분이 이걸 가지고 문제를 내셨는데, Dinic의 시간 복잡도 설명도 있으니 문제를 한번 보는 것을 추천한다. (문제 1 문제 2) 

10. Push-Relabel Algorithm 등 Dinic보다 빠른 알고리즘 역시 존재한다. 다만 대부분 굉장히 복잡하다. 아직 PS의 범위는 아닌 거 같다.

11. s - t Maximum Flow 외에도 모든 쌍 Maximum Flow를 구하는 경우도 필요할 것이다. 그냥 생각하면 V^2 * maxflow 지만, Gomory-Hu Tree라는 방법으로 V * maxflow에 구할 수도 있다고 한다. 난 잘 모르지만 페트르가 Amazing하다고 했으니 배워보자. Wikipedia Petr Mitrichev Blog 연습 문제 - CF 200E

12. Maximum Flow에서 용량에 상한 말고 하한이 걸려있는 경우를 생각해 볼 수 있다.  이 경우에는 조건을 만족하는 해가 존재하는지를 판별하는 것 부터가 쉽지 않다... 이를 만족하는 해가 존재하는지를 판별하는 문제를 Circulation Problem, 이 때 최대 플로우를 구하는 것을 Maximum Flow with Edge Demands 문제라고 부른다. L-R Maxflow라는 야매 용어도 있는데 보통 둘 다 뜻하는 용어다. 이 주제에 대한 설명은 다른 글에 정리했다.  2016년 대전 리저널 예선 / 본선 모두 Circulation Problem 관련 문제가 출제되었다. 

[Bipartite Matching]

13. 이분 그래프가 주어질 때, 최대 매칭을 찾는 문제이다. 현실 예시를 들자면 "남자 L명 여자 R명과 서로 좋아하는 이성 관계 쌍이 있을 때, 좋아하는 쌍을 최대 몇개 만들 수 있는가?" 정도가 있겠다. 최대 매칭 자체는 이분 그래프가 아닌 일반적인 그래프 (좋아하는 동성 관계 쌍이 있다던지..) 에서 다항 시간 알고리즘이 존재하지만 (Blossom Algorithm) 시간도 좀 느리고 코드가 매우 길다. 저것도 PS에서 안 나오는 알고리즘.

14. 하지만 이분 그래프에서는 Maximum Flow로 효율적으로 해결할 수 있다. 그래프의 두 정점 집합을 L / R이라 할 때 source에서 L로, L에서 R로 (에지가 있다면), R에서 sink로 capacity 1인 에지를 이어주면, Maximum Flow 모델링을 통해 Bipartite Matching의 크기를 구할 수 있다. 

15. 고로 플로우 그래프를 만들고, DFS/BFS와 Ford Fulkerson을 결합하면 O(fE) 에 풀 수 있다. 여기서 f <= V이기 때문에 O(VE)에 문제를 해결할 수 있다. BFS, DFS 모두 이분 매칭을 같은 시간 복잡도에 풀 수 있지만 DFS가 코드 사이즈나 실행속도면에서 약간 우수한 편이다. 특히, DFS로는 굉장히 짧은 코드로 풀 수 있는데 난 어떻게 하는지 모른다. 

16. 이분 그래프의 최소 정점 덮개 (Minimum Vertex Cover) 를 Bipartite Matching으로 구할 수 있다. 최소 정점 덮개는 일반 그래프에서 NP-Complete인 중요한 문제로, |최소 정점 덮개| = |이분 매칭 크기| 이다. 이분 매칭의 꽃이라고 할 수 있다. 이를 쾨닉의 정리 (Konig's Theorem)라고 부른다. 쾨닉의 정리 증명

17. Dinic's Algorithm을 사용해서 이분 매칭을 한다면 어떻게 될까? 일단 capacity가 다 1이니 blocking flow 찾는데 O(E)이고, iteration은 놀랍게도 Sqrt(V) 번만 돈다고 한다. 이걸 Hopcroft-Karp Algorithm이라고 부른다. 

18. IOI 2015부터 O(VE) 이분 매칭이 syllabus에 들어갔다. 근데 내 생각엔 아마 한동안 subtask 정도로만 나올거다..

[Min-Cost Max-Flow]

19. 유량 그래프에 cost가 붙은 상황에서 가능한 여러 맥스 플로우 중 최소 비용의 맥스 플로우를 구하는 방법이다.

20. 생각보다 풀이는 간단하다. 증가 경로를 최단 경로 알고리즘으로 탐색하면 된다. 다만 그래프에 음수 코스트 간선이 있기 때문에 Dijkstra를 그냥 돌리면 큰일나고 음수 간선을 처리할 수 있는 Bellman-Ford Algorithm을 사용해야 한다. 벨만 포드의 시간복잡도는 O(VE)이다.

21. ... 사실 제일 좋은 방법은 SPFA라는 흑마법 (?) 을 사용하는 것이다. 시간 복잡도는 O(VE) 이지만 실전에서 훨씬 빨리 돌아가는 알고리즘. 거의 V+E이다. 음수 간선에도 문제없이 돌아가기 때문에 MCMF랑 잘 맞는다. https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm

22. Max-Cost Max-Flow를 원한다면 음수 박고 똑같이 하면 된다. 맥스 플로우인건 상관없으니 비용만 최소화하고 싶을 수도 있다. 그럴 때는 벨만 포드 돌리다가 비용 0 이상 되면 그냥 끊어버리면 된다.

23. 역변을 만드는 과정에서 음수 사이클이 생기는 것이 걱정될수 있으나, 다행이도 초기 그래프에 음수 사이클이 없으면 음수 사이클이 절대 생기지 않음을 증명할 수 있다고 한다. 일반적인 모델링에서는 초기 그래프에 음수 사이클이 있을 수가 없다. (알려주신 hongjun7님 감사합니다.) https://www.acmicpc.net/board/view/1291

24. 특수한 모델링 상황에서는 음수 사이클이 존재해도 되고, 이 사이클을 양수 사이클로 바꿔가면서 플로우를 해결한다고 한다. 난 처음 들어봤는데 관련 문제를 보면 쓰겠다. 

25. 일반적인 상황에서의 복잡도는 O(f * VE) 이다. f가 붙으니 exponential이다. 다만 아직 일반적인 PS 범위에서는 이 정도로 충분한 거 같다. 학자들이 많이 연구한 문제인거 같고 poly time algorithm 역시 존재한다. 복잡도 O(V^3lgf) 알고리즘 -> 슬라이드 

26. 음수 간선을 적절히 처리하는 방법이 있는데 (Cycle Canceling) 이를 사용하면 벨만 포드 대신 Dijkstra를 사용할 수 있고 시간 복잡도는 O(V^3)이다. (대부분 완전그래프가 나오기 때문에 V^2 다익스트라를 사용한다.) 이 부분에 관심이 있다면 https://en.wikipedia.org/wiki/Johnson%27s_algorithm 를 참고.

27. 이 문제로 해결할 수 있는 대표적인 문제가 Assignment Problem(배정 문제) 이다. 이분 매칭의 MCMF판 일반화라고 할 수 있다. Assignment Problem은 Hungarian Algorithm을 사용해서 해결하는 것이 가능한데, MCMF가 Hungarian Algorithm의 일반화된 형태이기 때문에 충분히 이를 대체할 수 있다.

28. Assignment Problem은 이분 그래프에서의 MCMF로 변형시킬 수 있고 이 때 E = n^2, V = n이기 때문에 일반적으로 O(n^4)에 해결 가능하다. 하지만 Cycle Canceling을 사용해서 O(n^3)에도 해결할 수 있다. (naive가 n^4이고 slacky등을 잡아서 n^3으로 최적화하는 Hungarian Algorithm과 유사하다.) 일반적으로 Hungarian Algorithm이 MCMF보다 빠르게 작동하지만, 코딩하기는 MCMF가 훨씬 편하다. (헝가리안 알고리즘은 소스코드도 MCMF보다 길며 디버깅하기도 골치아프다) SPFA가 너무 강해서 MCMF가 느리다는 메리트도 상당히 덜한거 같다. SPFA가 선형으로 돈다 치면 N^3이니.