-
TAMREF's profile image
TAMREF
July 28, 2024
Grid Minor Theorem과 Erdős–Pósa Properties
Introduction : Erdős–Pósa Theorem Feedback Vertex Set (FVS) 이란, 그래프에서 $m$ 개 이하의 정점을 제거하여 forest로 만들 수 있는지를 묻는 문제입니다. 보다 엄밀하게, $G[V - X]$ 에 사이클이 존재하지 않는 $\lvert X \rvert \le m$ 이 존재하는지를 판별하는 문제입니다. 가령 아래 그래프에는 크기 2의 feedback vertex set $\lbrace B, D\rbrace$가 존재합니다. 일반적으로 FVS는 NP-complete 문제임이 알려져 있지만, 제거할 정점의 개수 $m$ 이 상수라고 가정하면 그래프의 크기에 대해서는 다항 시간에 해결할 수 있습니다. 예를 들어 $O(8^{m}...
-
TAMREF's profile image
TAMREF
May 21, 2023
Poly-logarithmic Randomized Bellman-Ford (2/2)
Introduction 지난 글에 이어 Bringmann 2023의 near-linear time shortest single source path (SSSP) 문제를 해결하는 부분을 더 다루어보도록 하겠습니다. 간선의 가중치가 $-W^{-}$ 이상인 weighted digraph에 대해 $\mathcal{O}(\log^{2} n \log(nW))$ 번의 dijkstra algorithm으로 shortest path tree, negative cycle 중 하나를 반환하는 문제입니다. 지난 글에서는 다음의 특수한 조건을 만족하는 Restricted SSSP (RSSSP)를 $\mathcal{O}(\log^{2} n)$ 번의 dijkstra algorithm으로 해결하는 Las-Vegas algorithm을 소개하였습니다. Definition. Directed graph $G$에 어떤 정점 $s \in V(G)$가 존재하여 다음을 만족하면 $G$를 restricted graph라고 한다....
-
TAMREF's profile image
TAMREF
April 22, 2023
Poly-logarithmic Randomized Bellman-Ford (1/2)
Introduction Single-Source Shortest Path (SSSP) 문제는 알고리즘 입문에서부터 다루는 아주 기초적이고, 또 중요한 문제입니다. 엄밀하게 적자면, $n$개의 정점과 $m$개의 가중치 있는 단방향 간선을 갖는 그래프 $G$와 시작 정점 $s$가 주어질 때, 모든 점 $i$에 대해 $s$에서 $i$로 가는 최단 경로의 길이 $\mathrm{dist}(s, i)$ 를 묻는 문제입니다. 일반적으로 가중치가 모두 양수인 경우에 사용할 수 있는 Dijkstra’s algorithm과 가중치의 값과 무관하게 사용할 수 있는 Bellman-Ford algorithm이 가장 유명합니다. 각각의 시간 복잡도는 $\mathcal{T}[\text{Dijkstra}]$: Practical한 선에서 $O(m \log n).$...
-
TAMREF's profile image
TAMREF
March 19, 2023
Near-Linear time Laplacian Equation Solver
Introduction Graph $G$의 Laplacian은 많은 graph problem에 관여하는 중요한 object입니다. 과거 Matrix-Tree theorem에 대해 다룬 글에서 볼 수 있듯 Laplacian의 determinant는 $G$의 스패닝 트리 개수와도 관계가 있고, 오늘 다룰 Laplacian system을 푸는 것도 굉장히 중요한 문제입니다. 또한 Laplacian의 고유값(eigenvalue)들 또한 graph의 well-connectedness와 관련이 있는 유의미한 지표로 사용할 수 있습니다. 정점이 $n$개, 간선이 $m$개인 무방향 그래프 $G$의 Laplacian $L _ {G}$는 $D - A$로 정의합니다. 여기서 $D$는 $D _ {i, i} = \deg(i)$를 만족하는 대각행렬이고, $A$는...
-
TAMREF's profile image
TAMREF
February 19, 2023
Treewidth Parametrized Dynamic Programming for Local Graph Problems
Introduction Vertex Cover, Independent Set, Dominating Set 등은 복잡도 이론에 관심이 있다면 익히 들어보았을 법한 문제들입니다. 각 문제의 정의는 다음과 같습니다. 무방향 단순그래프 $G = (V, E)$에 대해, Vertex Cover: 모든 $e = (u, v) \in E$에 대해 $u \in S 또는 $v \in S$를 만족하는 $S \subseteq V$를 찾아라. Independent Set: 모든 $u, v \in S$에 대해 $(u, v) \notin E$인 $S \subseteq V$를 찾아라. Dominating Set: 모든 $v \in V$에 대해 $v \in...
-
TAMREF's profile image
TAMREF
January 18, 2023
Deterministic Almost-Linear Time Edge Connectivity, with and without expander decomposition
Introduction 이곳에 글을 연재하기 시작할 즈음 두 개의 포스트에서 Minimum Cut 문제의 state-of-the-art라고 볼 수 있는 두 알고리즘을 소개했습니다. 하나는 적절한 random sampling을 통해 모든 min-cut을 sparse한 cut으로 근사한 Karger 2000에 대해 다루었고, 다른 하나는 almost-linear time complexity를 달성한 최초의 알고리즘인 Li 2021 에 대해 다루었습니다. 둘 다 “seminal work”이라는 표현이 아깝지 않을 만큼 좋은 논문이지만, 이 중 Li에 대해서는 Expander Decomposition에 대한 제 이해가 부족하여 논문의 outline만 짚고 넘어갔습니다. Li의 논문을 리뷰하며 스스로 느꼈던...
-
TAMREF's profile image
TAMREF
December 18, 2022
Using linear-optical quantum computing model to prove #P-hardness of Permanent
Introduction 지난 달 작성한 글과, 최근 진행하는 project-hardness 스터디를 진행하면서 $\sharp P$-hardness에 대한 내용을 자주 다루었습니다. 하지만 $\sharp P$라는 complexity가 고안된 근본적인 이유와도 같은 permanent에 대해서는 언급하지 않았습니다. Shortest Even Cycle Problem을 다룬 문제에서 지나가듯 이야기했지만 길게 이야기하지 않았죠. 실제로 이 문제를 해결한 Valiant(1979)의 논문은 3000회가 넘는 인용수를 기록했으며, Permanent를 비롯한 수많은 복잡도 이론에 대한 공헌으로 Valiant은 튜링상까지 수상하게 됩니다. 이런 위대한 업적에도 불구하고 Valiant이 어떤 아이디어로 Permanent의 hardness를 증명했는지는 비교적 알려져 있지 않은데, 문제...
-
TAMREF's profile image
TAMREF
November 8, 2022
The number of topological sorts in DAG, AND polytope centroid
Introduction 문제를 풀다 보면 “조건을 만족하는 해 $x$를 찾아라” 라는 문제는 쉽게 풀 수 있지만, “조건을 만족하는 해 $x$의 개수를 찾아라” 라는 문제가 유독 어려운 경우가 많습니다. 대표적으로 2-SAT은 다항 시간 안에 해를 찾을 수 있지만, 2-SAT의 조건을 모두 만족하는 해의 개수를 찾는 것은 매우 어렵다는 것이 알려져 있습니다. 비슷하게 이분그래프의 완전 매칭은 다항 시간 안에 찾을 수 있지만, 완전 매칭의 개수를 구하는 것은 permanent라는 계산하기 어려운 식과 동치가 됩니다. 오늘 다룰 주제는 Directed Acyclic...
-
TAMREF's profile image
TAMREF
October 20, 2022
Nearly optimal communication complexity of Bipartite Maximum Matching
Introduction Bipartite Maximum Matching (BMM)은 Bipartite graph $(V = X \sqcup Y, E \subseteq X \times Y)$에 대해 크기 $F$ 이상인 Matching이 존재하는지를 묻는 decision problem, 혹은 Maximum Matching의 크기를 계산하는 문제를 이야기합니다. 굉장히 오래 전부터 연구되어 온 문제이고, 정점이 $n$개, 간선이 $m$개인 BMM은 $m^{1 + o(1)}$ 시간 안에 해결할 수 있다는 것이 알려졌습니다. 원본 문제의 시간 복잡도가 subpolynomial 수준에서 사실상 optimum을 달성했기 때문에, 비전형적인 세팅에서 BMM을 해결하는 기법들이 등장하기 시작했습니다. 그 예시가 multi-party communication으로,...
-
TAMREF's profile image
TAMREF
September 9, 2022
Shortest Even Length Cycle in Digraphs
Introduction 문제 해결을 하다 보면 종종 몇 가지 조건들을 더하고 빼며 문제를 확장시키거나, 더 포괄적인 문제를 해결합니다. 지난 글 에서는 추상화를 통해 문제를 확장하는 일련의 과정을 느낄 수 있었습니다. 이번에는 반대로 원하는 답에 몇 가지 추가적인 조건을 덧붙여 구체화된 문제를 어떻게 해결하는지 들여다보도록 합시다. “단순 무방향 그래프 $G$에 사이클이 존재하느냐?” 라는 기초적인 질문에서 출발합니다. DFS를 이용하여 해결할 수 있는 문제죠. 이 문제만 해도 몇 가지 방향으로 확장할 수 있습니다. 최소 길이: “$G$에 길이가 $k$ 이하인...
-
TAMREF's profile image
TAMREF
August 18, 2022
Characteristic Polynomial in a Commutative Ring
Introduction $n \times n$ 정사각행렬 $A = (a _ {ij})$가 주어져 있을 때, $A$의 determinant $\det A$는 아래와 같이 계산할 수 있습니다. \[\det A = \sum _ {\sigma \in S _ {n}} \mathrm{sgn}(\sigma) \cdot \prod _ {i = 1}^{n} a _ {i \sigma _ {i}}\] 오늘은 $\det A$ 와, 그를 일반화하는 특성다항식(Characteristic polynomial) $\phi _ {A}(x) = \det(x I - A) = x^{n} - \mathrm{tr} (A) x^{n-1} + \cdots + (-1)^{n-1} \det A$를 계산하는 방법을...
-
TAMREF's profile image
TAMREF
June 19, 2022
ESPiRiT을 이용한 Sensitivity Computation
Introduction 지난 글에서는 MRI의 개괄적인 원리, 즉 장비에서 얻은 raw data를 어떻게 이미지로 변환하는지에 대해 다루어보았습니다. 또한 그 중에서 scan time을 줄이기 위한 기법인 Parallel imaging과, 그로 인한 이미지 퀄리티 저하를 보상하는 알고리즘 중 SENSE, GRAPPA, 그리고 PRUNO에 대해 간략히 다루었습니다. 현재 가장 두루 쓰이는 방법은 GRAPPA, SENSE이지만 이 둘은 벌써 고안된 지 20년이 넘어가는 classic한 알고리즘입니다. Practical하진 않지만, 연구나 다른 특수한 목적으로 개발된 고성능 알고리즘들이 쏟아져나왔죠. 오늘은 그 중에서 수학적으로도 흥미롭고, 꽤 재미있는 인사이트를...
-
TAMREF's profile image
TAMREF
April 19, 2022
Relevant points in Nearest-Neighbor Classification
Introduction $k$-nearest neighbor classification이란, $d$차원 공간 위의 point cloud들 (training set)과 그 class가 주어져 있을 때, 새로운 점의 class를 예측하는 한 가지 방법입니다. 자신과 가장 가까운 $k$개의 점의 label 중 가장 많은 것을 선택하는 방법으로, 고전적인 pattern recognition method 중 하나로 소개되었습니다. 오늘은 이 중 그나마 알고리즘의 시각에서 조명이 가능한 $k = 1$ case, 즉, nearest-neighbor classification에 대해 알아봅시다. 1-NN classification and Voronoi diagram $d = 2$인 경우, 어떤 점 $p$의 nearest neighbor가 $q$일 필요충분조건은...
-
TAMREF's profile image
TAMREF
March 20, 2022
Graph Distance Labeling Problem
Introduction 정점이 $N$개인 무방향 무가중치 그래프가 주어졌을 때, 아무 두 정점 $u, v$ 사이의 최단 경로의 길이를 질문(query)할 수 있는 자료구조를 만들고 싶다고 합시다. 일반적인 상황이라면 이 질문에 대한 답은 매우 간단합니다. Floyd-Warshall 알고리즘 등으로 정점의 최단 경로를 크기 $N \times N$ 배열 (lookup table) $d$에 저장하고, $d(u, v)$를 $O(1)$ 시간에 찾아주면 됩니다. 하지만 어떤 이유로 Lookup table $d$를 유지할 수 없다고 합시다. query time에 $d$를 접근하는 비용이 너무 큰 상황이나, 분산 네트워크 환경에서 중앙화된...
-
TAMREF's profile image
TAMREF
January 16, 2022
Faster Exponential Algorithm for Permutation Pattern Matching
Introduction “스택 수열”이라는 간단한 문제를 생각해 봅시다. https://www.acmicpc.net/problem/1874 이 문제는 스택을 이용한 시뮬레이션으로 해결할 수 있습니다. 요약하면, $[n] := {1, \cdots, n}$의 순열 $\sigma _ {1}, \cdots, \sigma _ {n}$이 주어졌을 때, $1, \cdots, n$을 순서대로 스택에 push(+)했다가 pop(-)하여 $\sigma _ {1}, \cdots, \sigma _ {n}$을 만들 수 있는지를 판별하는 문제입니다. 반대로 $\sigma _ {1}, \cdots, \sigma _ {n}$을 push-pop하여 $1, \cdots, n$으로 정렬할 수 있는지를 묻기도 하는데요, 이 경우에 $\sigma$를 stack-sortable permutation이라고 합니다. “스택...
-
TAMREF's profile image
TAMREF
December 19, 2021
MRI imaging과 Parallel Imaging Algorithm, 그리고 PRUNO
Introduction MRI (Magnetic Resonance Imaging)은 X-Ray, CT와 함께 널리 쓰이는 의료 영상 기법으로 손꼽힙니다. 이미지 특성 상 가장 좋은 연부 조직 대비 (soft matter contrast)를 보여줍니다. 즉, 근육이나 뇌 등 수분을 많이 포함하는 조직에 대해 가장 월등한 이미지 품질을 낼 수 있습니다. 다만 MRI의 경우 짧게는 30분에서 1시간 정도 되는 긴 촬영 시간이 단점으로 꼽히는데, 때문에 시간 단축을 위한 다양한 기법이 제시되고 있습니다. MRI는 촬영한 raw data가 전자기파 신호이기 때문에, 특이하게도 이를 푸리에 변환을 비롯한...
-
TAMREF's profile image
TAMREF
July 18, 2021
A Topological Approach to Evasiveness
스무고개 간단한 게임을 하나 생각해 봅시다. A와 B가 게임을 하는데, 아직 결정되지 않은 $n$자리 이진수가 있습니다. A는 B에게 $i$번째 비트가 $1$인지 물어볼 수 있고, B는 이를 답해줍니다. 질문을 $n$번보다 적게 써서 이 수가 $3$의 배수인지 맞힐 수 있다면 A의 승리, 그렇지 않다면 B의 승리입니다. 물론 B는 특정 수를 정해놓고 시작해야 하는 게 아니기 때문에, 질문에 따라 얼마든지 마음속으로 답을 바꿀 수 있습니다. 누가 승리할까요? leading zero 등의 제한 조건은 없습니다. 당연하게도, 이 게임은 B의 손쉬운...
-
TAMREF's profile image
TAMREF
May 16, 2021
Deterministic Mincut in Almost-Linear Time
Introduction 지난 3월 포스팅 “Minimum Cuts in Near Linear Time”에서 Weighted min-cut을 near-linear time에 구해주는 Karger의 Monte-Carlo algorithm을 소개한 적이 있었습니다. 이 글에서는 Karger의 알고리즘을 almost-linear complexity로 유지하며 derandomize하는 데 성공한 Jason Li의 2021년 논문 Determinstic Mincut in Almost Linear Time을 리뷰합니다. 논문 자체가 기술적으로 복잡한 부분이 많은 만큼, 깊숙한 디테일을 모두 다루기보다는 특별한 경우에 대해 이 논문에서 소개한 방법론이 어떻게 적용되는지를 다루어보도록 합니다. Terminologies 일부는 3월 포스팅과 동일하지만, Li (2021)의 문법을 대체로 따르면서 변화한...
-
TAMREF's profile image
TAMREF
April 18, 2021
Resistor Network와 Series-Parallel Graph Class
Introduction Childhood 중학교에서 전기 회로에 대해 배울 때를 떠올려 봅시다. “전압 $V$는 전류 $I$와 저항 $R$의 곱과 같다”는 옴의 법칙을 배운 뒤, 저항이 여러 개 연결되어 있을 때, 저항값이 같은 하나의 합성 저항으로 바꾸는 방법을 배웁니다. 바로 직렬 연결과 병렬 연결이죠. 직렬 연결. 저항 $R _ {1}$과 $R _ {2}$가 직렬로 연결되어 있다면, 합성 저항 $R _ {eq}$는 $R _ {eq} = R _ {1} + R _ {2}$를 만족한다. 병렬 연결. 저항 $R...
-
TAMREF's profile image
TAMREF
March 21, 2021
Minimum Cuts in Near-Linear Time
Introduction Weighted graph $G$에 대해, $G$의 min-cut 혹은 edge connectivity 는 $G$의 connected component가 둘 이상이 되도록 하기 위해 제거해야 하는 가중치 합으로 정의됩니다. 이름 그대로 네트워크를 단절시키기 위해 필요한 최소 비용으로, 수많은 파생과 응용이 가능합니다. 이 글에서는 $n$개의 정점, $m$개의 간선을 가진 weighted graph $G$의 min-cut을 near-linear time ($\tilde{O}(m)$)에 구하는 최초의 방법인 D. R. Karger의 Minimum Cuts in Near-Linear Time을 리뷰합니다. Definition 그래프 $G$는 non-negative weighted graph로 가정합니다. 즉, weight는 음 아닌 실수 값을...