테페리넷

사용자 도구

사이트 도구

현재 위치: 테페리넷 » Problem Solving » 최소 컷 (Minimum Cut)
ps:최소컷

목차

최소 컷 (Minimum Cut)

Global Minimum Cut

  • 무향그래프에서 최소개의 엣지를 제거해서 그래프를 둘로 나누는 방법을 찾는 문제. weighted 버전은 제거해야 하는 엣지의 가중치의 총합을 최소화하는 문제가 된다.
  • 크게 세가지 접근 방법이 있다 (https://koosaga.com/255 참고)
    • s-t min cut을 모든 s,t에 대해 찾기:
      • s-t min cut은 max flow를 찾는것과 같은 문제이다. HLPP를 쓴다면 O(V^2*sqrt(E)) 가 걸린다
      • 이것을 모든 s,t에 대해 찾아야 한다. 진짜로 그냥 돌리면 O(V^2)번 돌려야 하지만, Gomory-Hu 알고리즘을 쓰면 O(V)번만 돌려도 가능하다.
      • Gomory-Hu와 HLPP를 같이 써도 O(V^3*sqrt(E)).. 느리다
    • Edge contraction 접근
      • Karger's algorithm
        • Karger's algorithm, https://koosaga.com/71
        • 이하의 특성으로, Stoer-Wagner Algorithm 에 비해 장점이 없는것 같다. 그래서 굳이 몰라도 될거 같다
          • 제약 있음: Unweighted graph에서만 사용 가능하다
          • Randomized 알고리즘 → 오답 확률 있음
          • 속도 느림
          • 구현 난이도 별차이 없음
        • 기본적으로 Randomized 알고리즘이다. 한번 돌리는데에 O(ElogV)인데, 한번 돌려서 정답을 찾을 확률은 매우 낮다. 1/C(V,2) 의 확률.
        • 그래서 엄청 많이 돌려야 정답을 기대할수 있다. O(V^2logV)번 돌리면 오답률이 1/V 이하로 낮아진다.
        • O(ElogV)알고리즘을 O(V^2logV)번 돌리려면 O(V^2*E*logV)가 걸린다. Karger–Stein algorithm 은 이것을 발전시켜서 O(V^2*log^3(V))로 속도를 향상시켰다. 하지만 그래도 O(V^3)인 Stoer-Wagner Algorithm에 비해 큰 메리트가 없다.
      • Stoger-Wagner 알고리즘
    • Tree packing 접근
      • https://koosaga.com/255
      • Edge-disjoint spanning tree 들에서 컷을 찾아내는 방식인데.. 이론적으로는 이쪽이 가장 빠르다고 한다. PS에서 쓸일은 아직 없어보인다.
      • State-of-art는 deterministic 알고리즘의 경우, unweighted graph에서는 O(E*log^2(V)*loglog^2(V)), weighted graph에서는 O(VE) 에 동작한다고 한다

Stoger-Wagner 알고리즘

  • mincut phase에서 s-t mincut을 찾고, 얻은 s,t를 contraction 하는 작업을 O(V)번 반복한다
    • 이렇게 찾아진 mincut 값들중 최소값이 global mincut의 capacity이다
  • mincut phase는 프림 알고리즘과 비슷한 방식이라서, O(V^2) 또는 힙을 써서 O(ElogV)에 구현 가능. 그래서 총 시간복잡도는 O(V^3) 또는 O(VElogV)가 된다.
    • 보통 프림이나 다익스트라는 sparse 한 그래프를 대상으로 돌리는 경우가 많아서, 힙을 쓰는 O(ElogV) 구현이 일반적이다. 하지만 글로벌 민컷 관련해서 백준에 있는 문제들은 대부분 E=O(V^2)인 dense graph이다. 그래서 백준에서 문제를 풀기에는 힙을 안쓰는 구현이 더 유용하다
  • mincut에 해당하는 엣지를 찾는 방법
    • 보통 mincut의 capacity를 구하는 방법만 설명되어있고, mincut에 해당하는 엣지를 찾는 방법은 안 나와있는 경우도 많아서 찾는데 고생했다.
    • i번째의 mincut phase에서 구해진 s-t mincut의 용량이 값이 최소용량이었다고 하자. 이때의 t노드와 여태까지 (i-1번째 phase까지) t노드와 컨트랙션 되었던 노드들이 하나의 파티션을 이룬다. 당연히 이 노드들을 제외한 노드들이 다른 파티션을 이룬다. 이제 모든 엣지들 중에서 서로 다른 파티션의 노드들을 연결하는 엣지들만 찾으면 mincut의 엣지들이 된다.
    • 실제 구현은 i-1번째 phase까지 컨트랙션되는 노드 쌍들을 엣지로 이어서 그래프를 만든 다음에 i번째 phase에서 찾은 t노드와 연결된 노드들을 모두 하나의 파티션으로 두면 된다. 그래프탐색을 해도 되고 Disjoint set을 이용해도 된다.

구현 및 관련문제

  • s-t민컷 문제와 마찬가지로, 구하는 값은 여러가지가 될수 있다
    • 민컷의 캐퍼시티, 민컷에 포함하는 엣지들, 민컷으로 나뉘어진 두 노드 그룹
  • 그래서 함수 하나로 만들기 보다는 그냥 클래스로 만들었다.
  • 캐퍼시티만 구할때는, 그냥 contraction 한 노드쌍들을 리스트에 저장만 해둔다. partition이나 edge들을 구해야 할때는 저장해둔 contraction 히스토리를 Disjoint set으로 재구성해서 partition을 만든다.
  • O(n^3) 알고리즘이다 보니, 구현 디테일에 따라서 속도 차이가 좀 나는 편이다. 현재 백준에 스토어-바그너 태그로 들어있는 문제는 모두 4개인데, 이것들을 모두 풀기 위해서는 구현을 좀 신경써야 한다..
    • 13367: T<20, V<500, E<V(V-1)/2 이고, 제한시간 3초. (파이썬=2+3*3=11초)
    • 14060: V<100, E<3000 이고, 제한시간 2초.
    • 16230: V<500, E<V(V-1)/2, 제한시간이 추가시간없는 1초.
    • Colorgraph: V<250, E<V(V-1)/2, 제한시간 2초.
  • V<100 인 14060와 V<250인 13367과 16230 은 시간이 좀 빡빡하다.
    • cpp기준 1등 시간은 13367은 352ms, 16230은 140ms이다.
    • 처음 구현한 버전은 python으로 제출시 두문제에서 모두 TLE가 났다. 13367은 PyPy로 제출해서 4000ms 정도에 통과했지만, 16230은 Pypy로도 TLE였다.
    • 열심히 최적화한 결과 13367은 PyPy로 3500ms 정도로 단축시켰고, 이 버전을 16230에 제출해서 PyPy로 880ms 정도에 통과시켰다
    • 더 최적화를 해서 만든 최종버전은, 13367을 PyPy로 1500ms 까지 단축시켰다. 이제 Python으로 제출해도 8600ms에 통과했다. 16230의 경우에는 PyPy로 400ms, Python으로는 TLE.

토론

댓글을 입력하세요:
W S S K X
 
ps/최소컷.txt · 마지막으로 수정됨: 2023/11/29 15:12 저자 teferi