====== 이분 매칭 (Bipartite Matching) ======

  * 이분 그래프에서 최대 매칭을 찾는 문제를 이분 매칭이라고 부른다.

===== 이분매칭을 푸는 알고리즘 =====
  * 이분 매칭은 최대 유량 문제로 쉽게 변환해서 풀 수 있다. 
  * 그래프를 유량 그래프롤 변형해서 최대 유량 알고리즘을 적용해도 되지만, 이게 더 단순한 문제이다보니 (유량이 모두 1인 그래프) 최대 유량 알고리즘을 이분 그래프에 맞게 단순화시켜서 적용하는 것이 더 간단하고 효율적이다.
  * 최대 유량 문제와 비슷하게, worst case를 가지고 입력 제한을 주지 않는 경우가 많다. 알고리즘의 시간복잡도에, 노드와 엣지의 갯수를 대입해서 계산한 worst case로는 시간 내에 안돌아갈것 같지만, 그냥 돌리면 풀리는 문제들이 많다. 이 사실을 염두에 두고 아래를 보자.
    * 좀더 이론적인 설명을 찾은 것은, [[https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm#Analysis|위키피디아의 Hopcroft Karp 알고리즘 문서]] 에서인데, 평균적으로 스파스한 그래프는 높은 확률로 로그길이의 증가경로를 갖고, 그래서 이런 그래프에서는 Hopcroft Karp 알고리즘도 O(E*sqrt(V))가 아니라 O(ElogV)으로 돌아간다고 한다.

==== 포드-풀커슨 알고리즘 ====
  * 최대 유량 알고리즘 중, 임의의 증가경로를 한개 찾아서 업데이트하는것을 반복하는 포드풀커슨 알고리즘을 사용하면 O(fE)가 걸리는데, 이분매칭의 경우에는 f<=V 이므로 O(VE)가 걸린다. 
    * 일반적인 최대유량 문제에서는 augment path를 BFS로 찾는 에드먼드-카프 알고리즘을 사용하면 O(VE^2)의 더 효율적인 시간복잡도가 나오지만, 이분매칭에서는 똑같이 O(VE)이다. 그래서 굳이 BFS를 쓰는 것보다 그냥 DFS로 짜는 것이 실질적으로 더 빠르게 동작한다.
  * 이렇게 DFS로 짜는 방식을 [[https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html|CP-algorithm]]에서는 Kuhn's algorithm이라고도 부르고 있는데.. 국내 자료에서는 이렇게 부르는 것을 못본거 같다. 위키피디아에서도 그냥 포드-풀커슨 알고리즘을 이분 그래프에 적용한거 라고만 부른다.

==== 호프크로프트-카프 알고리즘 ====
  * 최대 유량 알고리즘 중에서 일반적으로 가장 빠른것은 Dinic 알고리즘으로 일반적인 그래프에서의 시간복잡도는 O(V^2E)이다. 이것은 BFS로 레벨그래프를 찾고 블로킹 플로우를 찾는 작업에 O(VE)가 걸리고, 이것을 최대 O(V)번 반복해야 하기 때문이다.
  * 그러나 모든 엣지의 캐퍼시티가 일정한 그래프에서는 블로킹 플로우를 O(E)에 찾을수 있고, 반복횟수는 최대 min(V^(2/3), E^(1/2))이 된다. 그래서 총 시간 복잡도는 O(E * min(V^(2/3), E^(1/2)))로 줄어든다
  * 그리고 이 Dinic 알고리즘을 이분매칭에 적용한 것이 호프크로프트-카프 알고리즘이다. 레벨그래프를 만들고 블로킹 플로우를 찾는 것이, BFS로 가장 짧은 증가경로의 길이를 찾고, 그 길이만큼의 모든 증가경로를 DFS로 찾아서 업데이트하는 방식으로 O(E)에 구현된다. 그리고, 이분그래프에서는 반복 횟수가 최대 O(V^(1/2))가 된다. 그래서 전체 시간복잡도가 O(sqrt(V)*E)가 된다.
    * 그냥 대강의 증명을 위해서 필요한 lemma들은, 
      * 1)길이가 가장 짧은 증가경로를 찾아서 업데이트하는 것을 반복할때, 찾아지는 증가경로의 길이는 감소하지 않는다. 2) i번째 증가경로와 i+1번째 증가경로의 길이가 같다면, 두 증가경로는 노드를 공유하지 않는다. => 이것들로부터 길이가 x인 증가경로들을 한번 이터레이션에서 모두 업데이트해주는 것으로 처리해도 알고리즘이 제대로 돌아간다는 것을 알수 있다.
      * 3) 증가경로들의 길이의 갯수는 최대 2*sqrt(V)이다. => 알고리즘의 이터레이션의 횟수가 O(sqrt(V))임을 보일수 있다.

==== 기타 알고리즘 ====
  * PS에서 쓸일은 없어보이지만..[[https://en.wikipedia.org/wiki/Maximum_cardinality_matching#Algorithms_for_bipartite_graphs|위키]]에 따르면, 
    * |V|대신에 매칭의 크기에 바운드되게 하는 살짝 더 빠른 알고리즘도 있다.
    * 스파스한 그래프에서는 O(E^(10/7))에 풀수 있다.
    * 플래너 그래프에서는 최대 유량 문제로 바꿔서 O(Vlog^3V)에 풀수있다
  * 레귤러 이분 그래프는 항상 퍼펙트 매칭을 가지므로 따라서 매칭의 크기는 그냥 항상 노드의 갯수와 같다. 매칭을 구하는 것은 O(nlogn)에 할수 있다는 것 같다.

==== 실제 실행 속도 ====
  * [[ps:problems:boj:3736]]은 V가 최대 20000, E는 문제 조건상으로는 최대 1억까지도 가능한 문제로 (실제 테스트 데이터에 저렇게 E가 큰 경우는 없는듯 하다), 그냥 DFS로는 안풀리고 호프크로프트-카프 알고리즘으로 풀어야 풀리는 문제이다. 
  * 그러나, 더 크기가 큰 문제에서는 호프크로프트-카프 알고리즘으로도 풀리지 않았다. [[https://judge.yosupo.jp/problem/bipartitematching]] 에서는 V와 E가 모두 20만개인 이분 그래프를 제공하는데, 호프크로프트-카프 알고리즘으로는 이것을 통과하는 것에 실패했다. 파이썬으로 이 문제를 푼 코드들은[[https://snuke.hatenablog.com/entry/2019/05/07/013609]] 에서 설명한 방법을 사용하고 있다. 
    * 이 방식도 한번의 BFS/DFS에서 여러개의 증가경로들을 찾아서 업데이트 해준다는 것은 호프크로프트-카프와 비슷하다. 그러나, 동작 방식이 다른 것이, 가장 작은 증가경로부터 업데이트 해주는 것을 보장하지 않는다. 그래서 O(sqrt(V)*E)의 시간복잡도가 되지는 않을것 같고 (적어도 위 방식 처럼은 증명이 안될듯.. 다른 방법으로 증명가능할지는 모르겠다) 그냥 O(VE)일것 같아 보이는데.. 실질적인 실행 속도는 더 빨랐다.
    * 최종적으로 teflib에 구현하는 것은 이 방법으로 했다. 출처 블로그에 있던 구현에 추가로, 단순한 휴리스틱으로 초기 매칭을 찾는 과정을 추가했다.
  * 속도를 좀더 비교해보면

^ 문제 ^   크기       ^ DFS ^ 호프크로프트-카프 ^ teflib ^
|[[ps:problems:boj:2188]] | V≤200, E≤200 | ? | 84ms | 192ms |
|[[ps:problems:boj:11365]] | V≤1000, E≤1000 | ? | 484ms | 408ms |
|[[ps:problems:boj:11014]] | V≤6400, E≤20000 | ? | ? | 292ms |
|[[ps:problems:boj:3736]] | V≤20000, E≤??? | X | 120ms | 216ms |
|yusupo | V≤200000, E≤200000 | X | X | 650ms |

    * 이렇게 보면 teflib에 구현한 방법이 가장 빠른게 맞다는 확신은 없지만.. 적어도 TLE가 나는 경우는 없었으니 이렇게 가도록 하자.

===== 관련된 문제와 정리들 =====
  * 참고: [[http://www.secmem.org/blog/2019/12/15/theorem-about-bipartite-matching/|최대 이분 매칭에 관한 몇 가지 정리 - S/W 멤버십 기술 블로그]]

  * 이분그래프에서 최소 버텍스 커버 ([[https://en.wikipedia.org/wiki/Vertex_cover|minimum vertex cover]])와 최대 독립집합([[https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Maximum_independent_sets_and_maximum_cliques|Maximum independent set]]을 이분 매칭으로 구할수 있다.
  * DAG에서의 최소 경로 커버와 최대 반사슬도 이분 매칭으로 구할수 있다.
  * 이런 문제들은 사실상 추가 지식이 필요하지만, 태그에는 이분매칭만 달려 있기 때문에 고생할수 있다..

==== 최소 버텍스 커버 / 최대 독립집합 ====
  * 쾨닉의 정리 ([[wp>Kőnig's theorem (graph theory)]] - 이분 그래프에서는 최소 버텍스 커버의 크기와 최대 매칭의 크기가 동일하다. 
    * 따라서 최소 버텍스 커버의 크기도 이분 매칭을 통해서 쉽게 구할수 있다.
    * 일반 그래프에서는 성립하지 않는다 -> 일반 그래프에서 최소 버텍스 커버를 구하는 것은 NP-complete이다.
    * 쾨닉의 정리의 증명에는 구성적인 방법과 LP dual을 이용한 방법이 있다
      * 구성적인 방법은 [[https://m.blog.naver.com/kks227/220967185015|kks 블로그의 이 포스트]]를
      * LP dual을 이용한 증명은 [[https://m.blog.naver.com/kks227/220977170159|kks 블로그의 이 포스트]]와 관련된 이전 포스트들을 쭉 따라가면 된다.
  * 최대 독립집합의 크기를 구하는 것은, 최대 독립집합이 최소 버텍스 커버의 여집합이기 때문에 가능하다. 
  * 정리하면
    * |최소 버텍스 커버| = |최대 매칭|
    * |최대 독립집합| = |V| - |최소 버텍스 커버| = |V| - |최대 매칭|
  * 관련 문제 - 최소 버텍스커버나 최대 독립집합을 구해야 하는 문제이지만 결국 모두 이분매칭 알고리즘을 돌려서 푼다.
    * [[ps:problems:boj:1867]] : 최소 버텍스 커버
    * [[ps:problems:boj:2414]] : 최소 버텍스 커버
    * [[ps:problems:boj:12843]] : 최대 독립집합
    * [[ps:problems:boj:11014]] : 최대 독립집합

=== 최소 버텍스 커버 구하기 ===
  * 최소 버텍스 커버의 크기만 필요한 것이 아니라, 최소 버텍스 커버의 원소들을 모두 찾아야 할때에는 다음과 같은 방법을 사용한다.
    * [[https://m.blog.naver.com/kks227/220967185015|kks 블로그]]
    * 1) 최대 매칭 M*를 구한다.
    * 2) 정점 집합 X를 구한다: L의 매칭되지 않은 정점들과, 그 정점으로부터 alternating path를 통해 도달할 수 있는 L, R의 모든 정점
    * 3) 최소 버텍스 커버 C* = (L - X) U (R ∩ X)
      * 즉, L의 정점들 중에서는 X에 미포함인 것들, R의 정점들 중에서는 X에 포함인 것들을 묶어 최소 버텍스 커버 C*를 구할 수 있다.
  * 코드는 tgraph.bipartite_matching() 에서 얻은 매칭 결과를 이용해서 이런식으로 구현할 수 있다.
    * <dkpr py>
from teflib import tgraph

def minimum_vertex_cover(bigraph):

    def dfs_rec(u, is_mvc):
        is_mvc[u] = False
        for v in bigraph[u]:
            if not is_mvc[v]:
                is_mvc[v] = True
                if (next_u := matched_node[v]) is not None and is_mvc[next_u]:
                    dfs_rec(next_u, is_mvc)

    matching = tgraph.bipartite_matching(bigraph)
    matched_node = [None] * len(bigraph)
    for u, v in matching.items():
        matched_node[v] = u
    is_mvc = [bool(edges) for edges in bigraph]
    for u, edges in enumerate(bigraph):
        if edges and u not in matching:
            dfs_rec(u, is_mvc)
    return [u for u, u_is_mvc in enumerate(is_mvc) if u_is_mvc]
</dkpr>
    * tgraph.bipartite_matching을 활용해서 구현하다보니, 이분매칭 과정에서 이미 구했던 matched_node 리스트를 minimum vertext cover를 구하기 위해서 다시 만들어야 하는 등, 다소 비효율적인 부분은 있다.
  * 관련 문제: [[ps:problems:boj:2051]]


==== 최소 경로 커버 / 최대 반사슬 ====
  * DAG에서 최소 경로 커버 (Minumum Path Cover)은 DAG(Directed Acyclic Graph)에서 모든 정점을 커버하는 겹치지 않는 최소의 경로의 수를 구하는 문제이다.
    * 참고 : [[https://blog.naver.com/jqkt15/222058427237]] [[https://gazelle-and-cs.tistory.com/52]]
    * 이 문제를 이분 매칭으로 변환하는 방법은 다음과 같다.
      * 원래 DAG의 노드 갯수 * 2 개의 노드로 이루어진 이분 그래프를 만든다
        * 원래 DAG에 v_1~v_n 까지의 노드가 존재했다면 l_1 ~ l_n, r_1 ~ r_n 의 노드를 갖도록 한다.
        * DAG에 존재하는 엣지 v_i => v_j 에 대해서 l_i 와 r_j 를 연결하는 엣지를 만든다.
      * 이분 그래프에서 매칭된 엣지들은 DAG에서 패스를 구성하는 엣지들이 된다. 
        * 패스의 갯수는 n - {이분매칭의 크기} 가 된다.
        * 각 패스의 시작점에 해당하는 노드들은, l_1 ~ l_n 중에서 매치되지 않는 노드들이다.
        * 각 패스의 끝점에 해당되는 노드들은, r_1 ~ r_n 중에서 매치되지 않는 노드들이다.
  * 부분 순서 집합에서의 최대 반사슬(Maximum Anti Chain)은 위상관계가 없는 정점들로 이루어진 최대 크기의 집합을 구하는 문제이다.
    * 참고 : [[https://blog.naver.com/jqkt15/222062117806]]
    * 딜워스의 정리([[wp>Dilworth's theorem]])는 부분순서집합(POSET; Partially Ordered Set)에서 최대 반사슬의 크기가 최소 경로 커버의 크기와 같다는 정리이다.
    * 따라서 최대 반사슬의 크기도 이분 매칭을 이용해서 구할 수 있다.
      * POSET으로 문제가 주어진 경우에는, transivity를 적용해서 DAG를 만든 다음에, 최소 경로 커버에서 설명했던것처럼 다시 이분그래프를 만들어서 이분 매칭을 돌리면 된다.
      * 최대 반사슬의 크기 역시 n - {이분매칭의 크기} 가 된다.
      * 최대 반사슬 집합을 찾을 때에는, 최소 버텍스 커버의 여집합을 구해주면 된다.
        * l_i와 r_i가 모두 최소 버텍스 커버에 포함되지 않는 v_i들의 집합을 구하면 된다.
        * 좀더 자세한 설명과 증명: [[https://tamref.com/145]]
  * 관련 문제
    * [[ps:problems:boj:13503]] : 최소 경로 커버
    * [[ps:problems:boj:3295]] : 최소 경로 커버
    * [[ps:problems:boj:13411]] : 최대 반사슬의 크기
    * [[ps:problems:boj:8898]] : 최대 반사슬 집합 구하기


==== 홀의 결혼 정리 ====
  * [작성중]

===== 문제풀이 테크닉 =====

==== 한 노드에서 여러개의 노드로 연결이 가능할 때 ====
  * 매칭의 정의상, 한 노드에 연결된 엣지는 한개만 존재해야 한다.
  * 따라서 그래프를 그대로 둔 상태에서는 한 노드를 최대 k개의 노드와 연결시키는 문제는 매칭으로 풀수가 없다.
  * 이분 매칭을 플로우 문제로 변형하는 기본 방식을 적용하면, 시작 노드에서 왼쪽 그룹의 노드들까지의 유량을 k로 설정함으로써 이 문제를 최대유량 문제로 만들수 있고, 최대유량 알고리즘으로 풀수 있다.
  * 하지만 k가 작을경우 (2~3정도)에는 그냥 동일한 노드들을 k개씩 만들어서 그래프를 만든 뒤, 그냥 이분매칭으로 푸는 방법이 가능하고, 더 빠르다.
  * 관련 문제: 
    * [[ps:problems:boj:11376]]
    * [[ps:problems:boj:1671]]

==== 그리드를 이분그래프로 모델링 ====
  * 몇가지 유형이 있다.

=== 각 셀을 노드로 모델링 ===
  * 제일 직관적이다
  * 문제에서 인접한 셀 또는 특정 위치 관계에 있는 셀들 간에 제약 조건이 들어가게 되면, 이 위치 관계에 있는 셀들 사이에 엣지를 추가해서 그래프를 만들면 된다.
  * 위치 관계에 따라서 이분 그래프가 만들어지는 경우에는 이분 매칭을 사용할수 있게 된다.
  * 관련 문제
    * [[ps:problems:boj:11014]]: 이렇게 만들어진 이분그래프에서 최대 독립집합을 찾는 문제

=== 각 셀을 엣지로 모델링 ===
  * 행과 열을 노드로 만들고, 셀을 행노드와 열노드를 잇는 엣지로 모델링할수 있다.
  * 관련 문제
    * [[ps:problems:boj:1574]]: 최대한 많은 셀을 고르는 문제이므로, 최대한 많은 엣지를 찾는 이분 매칭 문제가 된다
    * [[ps:problems:boj:2414]]: 최대한 적은 행 또는 열을 골라서 모든 셀을 커버하는 문제다. 이 모델링에 의하면 모든 엣지를 커버하는 최소한의 노드를 찾는 문제이므로 최소 버텍스 커버 문제가 된다.
    * [[ps:problems:boj:1799]]: 행과 열이 아니라, 대각선들을 노드로 만들게 되지만 기본 원리는 동일하다.

=== 인접한 셀 사이의 테두리를 노드로 모델링 ===
  * 그리드를 특정 타일들로 채우는 문제들의 경우, 각 테두리가 타일 내부에 있게 될지 타일의 테두리에 있게 될지를 결정하는 문제로 바꿀수 있다.
  * 테두리들을 노드로 만들고, 타일의 형태에 따라서 엣지들을 만들었을때 이분 그래프가 된다면, 타일링 문제를 이분 매칭으로 바꿔서 풀수 있는 경우가 있다
  * 관련 문제
    * [[ps:problems:boj:14930]]

==== 에지에 가중치가 있고, 매칭에서 최대 가중치를 최소화 시키는 문제 ====
  * 보통은 가중치가 x이하인 엣지들만으로 그래프를 구성할때 퍼펙트 매칭을 만들수 있는 x의 최소값을 찾는 문제가 된다.
  * 이분 탐색으로 x의 값을 찾을 수 있다.
  * 관련 문제
    * [[ps:problems:boj:1348]]