내용
- 다루는 모든 그래프는 방향성 가중치 없고 연결되었다고 가정
- Cactus는 임의의 서로 다른 사이클 쌍을 잡았을 때 겹치는 간선이 없는 무방향 그래프를 뜻한다. Cactus의 min-cut은 절선이 있으면 1이고 아니면 2다.
- 임의의 그래프 G에 대해서, 선인장 H 그리고 전사함수 f : V(G) → V(H) 의 쌍 (H, f)가 존재해서
- G의 모든 민컷이 H의 모든 민컷에 대응되고, H의 모든 민컷이 G의 모든 민컷에 대응되게 할 수 있다.
- 이게 무슨 말이냐면, f가 전사함수니까 결국 H의 각 정점은 G의 정점의 “partition” 같은 것임을 알 수 있다. H의 정점을 이제 편의상 bag라고 부른다. 당연한 소리지만 한 bag에 정점 하나 이상 있고 합집합은 전체며 한 정점은 정확히 한 bag에 속함
- 일단 G의 임의의 민컷 X에 대해서, H의 어떠한 민컷 Y가 존재해서, Y의 bag의 합집합이 정확히 X이다.
- 반대로, H의 임의의 민컷 Y에 대해서, Y의 bag의 합집합을 취하면 그것은 G의 민컷이다.
- 근데 이 결론은 이상하다. 만약 그러한 선인장이 존재한다고 하자. 그러면 민컷은 절선을 고르거나 선인장의 같은 사이클 상 두 간선을 골라야 하니 |사이클|^2 개 밖에 존재할 수 없다.
- 그러면 민컷의 개수가 지수적이지 않고 n^2개다? 부터 이상하다
- … 라고할뻔. 민컷의 개수는 항상 n(n-1)/2 개 이하이다. 이 Fact의 독립적인 증명은 Karger-Stein algorithm을 통해서도 가능하다.
- 이 cactus representation은 Kar00 비슷하게 Near-linear하게 찾을 수 있다 http://people.csail.mit.edu/karger/Papers/soda09-cactus.pdf
- k가 작은 경우에 대해서 이 fact를 revisit해보자. mincut = 1일때는 obviously true다 (cactus 말고 tree 형태의 representation을 얻을 것
- mincut = 2일 때는 H의 간선 집합이 G의 간선 집합의 부분집합이다. https://arxiv.org/pdf/2105.01699.pdf Thm 3.1
- 즉, mincut = 2일때는 각 bag이 3-connected component가 된다. 3-connected component로 그래프를 분해하는 결과가 이렇게 되는 것
- H의 간선 집합이 G의 간선 집합의 부분집합이라는 이야기를 조금 더 정확히 하면, H의 간선 집합 == (G에서 임의의 2-edge cut에 속하는 간선들의 집합) 과 동일하다고 보면 된다. 즉 2-edge cut이 아닌 간선들은 같은 bag에 있고 아닌 간선들은 모두 보존
- 그래서 이 때는 cactus representation을 구하면 2-edge cut의 characterization도 바로 얻을 수 있다.
- 역으로 triconnected component를 구하면 cactus representation을 얻을 수 있다고 생각할 수도 있다.
- 관련 문제: https://old.yosupo.jp/problem/three_edge_connected_components https://codeforces.com/contest/1648/problem/F
출처: https://koosaga.com/288 [구사과:티스토리]