20220307 노트: Pisinger algorithm, SPQR tree, Cactus representation of cuts

Pisinger Algorithm

• Subset Sum 문제는, positive integer multiset S와 정수 t가 주어졌을 때, 합이 t인 S의 부분집합이 있는지를 찾는 문제이다.
• S의 원소 범위가 1 이상 M 이하의 정수라고 가정하자. $M$ 에 대한 dependency가 없이 풀려면 당연히 NP-hard이다.
• 그냥 DP를 하면 $O(n^2M)$ 이다.
• 각 숫자를 prefix sum으로 처리하면 $O(nM^2)$이다.
• Generating function으로 $O(nM \log nM)$ 에 푸는 풀이가 비교적 최근에 발견되었다.
• 꽤 깔끔한 $O(nM)$ 풀이를 서술
• 일단 첫 번째 Lemma는, 이 문제를 모든 수가 [-M, M] 인 multiset S에서 합이 1 <= t <= M 이 되는 subset을 찾는 문제로 변형할 수 있음
• 이건 쉽게 보일 수가 있는데, 합이 t가 될 때까지 greedy하게 아무거나 고르면 됨
• 그래서 합을 정말 t로 만들었으면 잘 된거고
• 아니면 t - 1 이하의 무언가일텐데, 만약에 t-M 이하면 고를 게 없었다는 뜻이니까 실패한거고
• 아니면 고른 것에 음수, 안 고른 것에 양수 취한다음에, t - (지금 고른 집합) 을 목표로 하는 subset을 찾으면 됨
• 음수 (고른 것) 들을 {a_1, a_2, \ldots, a_n} 양수 (안 고른 것) 들을 {b_1, b_2, \ldots, b_m} 라고 하면 (a_i < 0 < b_i)
• 여기서 합이 1 <= t < M 인 걸 양쪽에서 고르는 문제
• DP[i][j][k] 를 a[1..i] b[1..j] 에서 합이 k인걸 고를 수 있는지를 저장하는 boolean 테이블이라고 하면
• 여기서 1 <= k <= 2M 인 것만 봐도 됨.
• 왜냐? 0 이하로 내려갈정도로 마이너스를 너무 많이 먹었으면 어차피 플러스를 먹어야 하니까 j를 늘려서 플러스를 먹어서 올리고 2M 초과일때도 i를 늘려서 마이너스를 먹어서 줄일 수 있으니까
• 이때 복잡도는 $O(n^2M)$
• 이제 여기서 상태 바꾸는 트릭을 사용. DP[i][j][k] -> DP[i + 1][j][k] 이니까, F[j][k] = (DP[i][j][k]가 참인 최소 i) 라고 정의
• 그리고 이제 DP의 상태 전이는 전부 부등식으로 나오는데
  • F[j][k] >= F[j + 1][k]
  • F[j][k] >= F[j + 1][k + b[j]]
  • For all i >= F[j][k], i + 1 >= F[j][k + a[i]]
• 다 좋은데 마지막 항이 불편
• 근데 여기서 F[j][k] >= F[j + 1][k] 라는 항에 주목하면
• F[j - 1][k] >= F[j][k] 니까 내가 이걸 j가 증가하는 순서대로 채워나갔다. 라고 하면
• For all i >= F[j - 1][k], i + 1 >= F[j - 1][k + a[i]] >= F[j][k + a[i]] 이라는 것이 앞 단에서 이미 다 보존됨
• 그래서 저 루프를 F[j - 1][k] … N 에 대해서 다 돌리는 건 낭비이고 F[j - 1][k] > i >= F[j][k] 에 대해서만 돌리면 됨
• 그러면 투 포인터랑 동일한 이유로 Amortized O(nM)
• 그래서 가중치 (M) 혹은 무게 (W)가 constant bounded된 subset sum / knapsack 문제는
  • subset sum: O(n^2M) (naive), O(nM^2) (prefix sum) O(nM) (pisinger99)
  • knapsack: O(n^2M) (naive), O(nMW) (pisinger99), O(nM^2) (https://www.acmicpc.net/problem/13058 + SMAWK = https://arxiv.org/pdf/1802.06440.pdf)

SPQR Tree

• SPQR tree를 사용하면 그래프의 모든 2-vertex cut을 characterize할 수 있음
• Block-cut tree가 그래프의 모든 cut vertex를 characterize하고, 그래프를 2-connected component로 나누는 것 처럼 SPQR tree는 그래프의 모든 2-vertex cut을 characterizze하고, 그래프를 3-connected component로 나눌 수 있음
• 이와 별개로 그래프의 triconnectivity를 near-linear하게 판별하는 건 간단한 편
• SPQR tree의 base case는
  • Q. 간선 1개
  • R. triconnected graph
• recursion case는
  • S. Series: sub-SPQR tree들을 간선으로 대체하면 사이클이 됨
  • P. Parallel: sub-SPQR tree들을 간선으로 대체하면 두 점을 잇는 중복 간선들이 됨
  • (사이클이 직선이 아니라는 것 외에는 series parallel graph의 정의와 유사)
• SPQR tree 자체는 linear하게 build할 수 있고, incremental setting 에서도 near-linear하게 작동할 수 있음
• decremental setting에서도 되는데, planar-graph라는 precondition이 붙음 https://hal.inria.fr/hal-01925961/document
• 여기서 내릴 수 있는 가장 쉬운 결론은, near-linear time에 incremental하게 2-vertex cut을 관리할 수 있는 자료구조가 존재한다는 것.
• (참고로, offline setting에서는 near-linear time에 k-connectivity를 관리할 수 있기는 함. https://arxiv.org/abs/1910.10359)
• .. 여기까지가 SPQR tree를 connectivity라는 관점에서 본 결과인데, 실제로 SPQR tree 자체의 진가는 planar graph와 연결되었을 때 나온다.
• planar graph와 triconnectivity가 관련이 있는 이유는, 3-connected planar graph에서는 embedding이 unique (up to reflection) 하기 때문.
• 고로 SPQR tree는 planar graph의 모든 가능한 embedding을 표현하는 자료구조로 해석할 수 있다.
• 이걸로 두 문제를 풀 수 있는데
  • indegree 0인 유일한 정점 s, outdegree 0인 유일한 정점 t가 같은 face에 속하는 directed planar graph를 planar s-t graph라고 함. 여기서는 DFS preorder/postorder를 가지고 O(1) 에 reachability를 판별할 수 있음이 잘 알려져 있음.
  • planar graph에서 edge update가 있을 때 MST 관리
• 결론부터 말하면 이 두 문제를 모두 incremental setting에서 O(log n) 에 해결 가능.
• 개략적으론 이런 식이라고 함. 이 두 문제는 만약에 Embedding이 고정되어 있고 추가되는 간선의 양 끝점이 같은 face에 있는 경우 쉽게 해결을 할 수 있는데, SPQR tree를 사용하면 이 조건이 없어도 똑같은 조건에 해결할 수 있음.
• 원저는 못 구했고 Extended Abstract라서 이에 대한 설명이 없음. 내 추측은 이런 식일 것 같은데, 추가되는 간선의 양 끝점이 같은 face에 없다면 SPQR tree를 그렇게 되도록 rotate해서 (BST처럼 사용) 같은 face에 있도록 하거나 아니면 그것이 절대 불가능함을 보임. 그렇게 되면 두 문제에서 요구하는 조건이 충족되어서 해결 가능
• 결국 이 라인에서 얻어갈 수 있는 점은, SPQR tree는 planar graph의 모든 가능한 embedding을 표현하는 자료구조로 해석할 수 있다 -> SPQR tree를 planar graph의 어떤 embedding을 보존하는 자료 구조로 해석할 수 있다 로 볼 수 있는 것이고
• 이렇게 되면 결국 embedding이라는 것을 트리의 형태로 표현할 수 있는 방법을 얻게 됨
• https://arxiv.org/pdf/1911.03449.pdf 그래서 fully-dynamic planarity 문제에서도 SPQR tree가 주는 representation을 활용

Cactus Representation of Min Cut

• 다루는 모든 그래프는 방향성 가중치 없고 연결되었다고 가정
• 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