구사과

어떤 decision problem에 대해서, kernel은 그 decision problem의 답을 보존하는 작은 인스턴스다. 그러니까 f : Instance -> Instance인데$|f(x)| \leq g(k)$$Decision(x) = Decision(f(x))$같은 함수가 있으면, decision problem은 $g(k)$ 크기의 kernel이 있다고 함자명한 theorem은, 모든 FPT 문제는 다항시간에 찾을 수 있는 kernel이 존재한다는 것이다.구체적으로 decision problem을 $g(k) n^c$ 에 풀 수 있으면 poly time에 kernel을 찾을 수 있음. 방법은:$n \geq g(k)$ 면, 그냥 $n^{c+1}$에 풀고 trivial yes / no instance..

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 E$For 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 E$For 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..