2019년 APIO 2019 B번 문제 Bridges의 Almost linear time 풀이가 존재하는지에 대해서 질문을 남긴 적이 있다. 당시의 나는 그러한 풀이가 존재할 것이라고 믿었다. Dynamic MST를 Poly-log time에 해결할 수 있기 때문이다. 하지만 이제는 다시 한 번 생각해 봐야 할 것 같다. 문제를 요약하면 다음과 같다. (원래 문제에서는 트리가 아니라 그래프가 주어지지만, 여기서는 트리라고 가정하고 Hardness를 증명한다. 즉, 문제 상황보다 더 강한 증명이다.)크기 n 의 가중치 있는 트리가 주어졌을 때, 다음 두 연산을 처리하여라:Update(e, w): 간선 e 의 가중치를 w 로 갱신한다.Query(v, x): 정점 v 에서 가중치 x ..
잠자고 있던 퀄리티 낮은 scribe 몇개를 기록용으로 올린다.Hamiltonian Path in O(2^nn^c) time, O(n^c) spaceKarp의 1982년 논문이라고 들었다.존재 여부 대신 경우의 수 mod p를 세자. random p를 잡아서 decision problem으로 바꿀 수 있다.길이 n의 (simple) path를 세는 대신 길이 n의 walk를 세는 건 쉬움. 그냥 sumA^{n-1}(i, j). 그런데 길이 n의 walk가 모든 정점을 방문하면 그게 hamilton path이다. 그래서 모든 정점 부분 집합에 대해서 포배하면 끝.TSP in O(4^n n^c) time, O(n^c) space모든 i, j 에 대해 i 에서 출발해서 모든 정점을 다 돌..
출처는 http://www.cs.tau.ac.il/~zwick/grad-algo-09/short-path.pdf흔히 알려진 알고리즘은 벨만 포드를 사용한 O(nm) 시간 알고리즘이다. 이 글에서는 O((n + m)\sqrt n \log W) 알고리즘을 소개한다.그래프에 음수 사이클이 없다면 퍼텐셜 함수가 존재해서 p(u) - p(v) + w(u, v) \geq 0 이 되게 만들어 줄 수 있음이 잘 알려져 있다. 그래서 결정 문제를음수 사이클을 찾거나퍼텐셜 함수를 찾거나로 정의할 수 있다. 퍼텐셜 함수를 찾을 수 있으면 거기서부터는 O(m + n \log n) 에 최단 경로를 찾는 것이 쉽기 때문이다.만약 모든 간선의 가중치가 -1 이상 (즉 음수 간선은 무조건 가중치 -1) 일 때 문제를 ..
예전에 남부순환로 문제를 출제할 때 Mergeable heap에 관해서 사람들과 논의하던 때가 있었는데, Leftist heap / Randomized mergeable heap 모두 딱 와닿는 느낌의 논증은 없었던 것 같다. 최근에 Skew heap이라는 걸 접했는데 굉장히 짧고 아름다운 논증이 존재해서 소개한다. (아쉽게도 Worst-case bound가 아니라 남부순환로 문제에는 사용할 수 없다. 이론적으로는.)목표는 Merge 연산을 Amortized O(\log n) 에 수행하는 것이다. 이것만 수행하면 Init, ExtractMin은 따라온다.두 트리를 머지할때 오른쪽 자식을 따라서 path를 타고 가자. 이 path를 따라 적힌 값들은 증가한다. 고로 이 path를 따라서 merge so..

Part 1. Uniform SamplingGiven an undirected unweighted graph G = (V, E), A (1 \pm \epsilon) cut sparsifier H = (V, F, w) satisfies the following:F \subseteq EFor all \emptyset \subsetneq S \subsetneq V it holds that \delta_w(H, S) \in [(1 - \epsilon)\delta_{\mathbf{1}}(G, S),(1 + \epsilon)\delta_{\mathbf{1}}(G, S)]This is a sparsification that preserves the cuts. Compare this to the ..
Given an undirected unweighted graph G = (V, E), A (1 \pm \epsilon) cut sparsifier H = (V, F, w) satisfies the following:F \subseteq EFor all \emptyset \subsetneq S \subsetneq V it holds that \delta_w(H, S) \in [(1 - \epsilon)\delta_{\mathbf{1}}(G, S),(1 + \epsilon)\delta_{\mathbf{1}}(G, S)]This is a sparsification that preserves the cuts. Compare this to the distance spanner, which ..
Undirected graph G = (V, E) 에 대해, G의 t-spanner H = Spanner(G,t) = (V, E^\prime) 는 다음 성질을 만족한다: E^\prime \subseteq E 모든 u, v \in V 에 대해, dist(H, u, v) \le dist(G, u, v) \times t E^\prime 의 크기가 작음 즉, 최단 경로를 Approximate하게 보존하는 Sparsification이다. Equivalent하게, 다음과 같이 표현할 수도 있다. E^\prime \subseteq E 모든 (u, v) \in E 에 대해, dist(H, u, v) \le dist(G, u, v) \times t E^\prime 의 크기가 작..
Example 1 (https://koosaga.com/319 마지막 단락) 그래프가 주어질 때 이 그래프의 maximal independent set 을 구하는 문제를 생각해 보자. maximal independent set은 maximum independent set을 approximate할 수 없다. 하지만 maximal matching과 \Delta+1 edge coloring을 구하는 데 사용할 수 있고 이들은 각각 그들의 optimal variant의 constant approximation이다. 다음 과정을 정점이 1개 이상일 때까지 반복하면 된다: 각 노드에 [0, 1] 사이의 random real을 배정한다. 이를 r(v) 라고 하자. 만약 어떠한 노드에 대해 $\max_{w ..

https://dl.acm.org/doi/pdf/10.5555/982792.982916 Cut-cycle duality에 의해 G 에서 minimum cut을 찾는 것은 G^* 에서 minimum cycle을 찾는 것과 동일하다. 아이디어는, G^* 에서 적당한 사이클 C를 찾은 다음, C의 *안* 과 *밖* 에 대해서 분할 정복을 하고, 이후 C의 안과 밖을 오가는 사이클을 찾는 것이다. 분할 정복이 성립하려면 일단 C가 G^* 의 Face들을 공평하게 쪼개야 할 것이다. 이런 C는 O(n) 시간에 찾을 수 있다. G^* 의 모든 Face를 대각선에 \infty 가중치 간선 넣고 대충 triangulate하자. 다음, G^* 에서 아무 정점을 잡고, sho..
https://arxiv.org/pdf/2211.09606.pdf 생각보다 내용이 많이 쉬워서 살짝 날먹이라고도 생각했다. 일단 핵심 내용은 다음과 같은 알고리즘의 존재성이다: s, t flow가 T 이하일때까지 s, t flow를 incremental하게 관리하는 O(Tm) 알고리즘이 존재한다. 일단 이 알고리즘에 대해서 논의하기 전에, 이러한 알고리즘이 존재하면 어떻게 전체 문제를 해결할 수 있는지 살펴보자. 플로우의 값이 T 이하일 때까지는 O(Tm) 알고리즘을 돌린다. 플로우의 값이 T 를 넘어갔을 때는, 일단 플로우의 값이 T 라고 하고 계속 간선 삽입 쿼리를 받자. 플로우의 값이 T (1 + \epsilon) 을 넘어가면 위 값이 틀리게 된다. 이것이 일어나려면..
- Total
- Today
- Yesterday