티스토리 뷰

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 문제는

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

'공부 > Problem solving' 카테고리의 다른 글

Treewidth를 사용한 PS 문제 해결  (3) 2022.07.17
Push Relabel Algorithm (2)  (1) 2022.04.17
Push Relabel Algorithm (1)  (0) 2022.02.15
2021.12.02 problem solving  (0) 2021.12.02
2021 ICPC Seoul Regional  (0) 2021.11.23
댓글
공지사항
최근에 올라온 글
Total
Today
Yesterday