-
Irrelevant Vertex Technique
서론 지난 두 편의 글에서 $\mathcal{F}$-deletion 문제에 대해 살펴보았다. $\mathcal{F}$-deletion 문제의 optimal FPT 알고리즘에서는 큰 flat wall 중심부에 irrelevant vertex가 존재한다는 사실이 매우 중요한 요소로 사용되었다. Irrelevant vertex technique은 Graph Minor Theory에서 등장하는 일종의 ‘축소’ 기법으로, Robertson과 Seymour의 Graph Minors 논문 시리즈에서 처음 등장했다. 이는 그래프에서 특정한 패턴 혹은 구조를 찾는 문제들에서 활용되며, 다음의 아이디어에 기반한다: 어떤 문제에 대해 $G$ 안에 찾고자 하는 구조의 존재 여부에 전혀 영향을 주지 않는 정점 $v$가 존재한다면, $v$를 삭제해도...
-
Phase Transitions in Networks: Scale-free Networks
0. Introduction 상전이(phase transition)는 물리학에서 나온 개념으로, 어떤 임계점을 기준으로 양쪽에서 행동이 달라지는 것을 말합니다. 물리학을 공부하는 경우 이러한 현상을 학습하게 되는데요, 대표적인 예시로 2차원 이징 모델이나 란다우 긴즈버그 모델 등이 있습니다. 놀랍게도 어떤 랜덤하게 구성한 네트워크들에 대해서도 이와 비슷한 상전이 현상이 일어남이 알려져 있습니다. 이전 글에서는 랜덤 네트워크 모델 중 모든 가능한 간선들이 연결되어있을 확률이 $p$로 일정한, 가장 간단한 모델인 Erdős–Rényi 모델에서 일어나는 상전이에 대해 알아보았습니다. 또한 이 모델이 클러스터링 문제(두 이웃이 서로 이웃일...
-
Concurrent Queue - LCRQ
Intro Concurrent queue는 locks, databases, load balancers / task schedulers, transaction logging, HFT, network packet processing 등에서 사용됩니다. 수십 개의 스레드가 동시에 enq/deq를 수행하면서 좋은 throughput을 유지하도록 조율하는 것은 쉽지 않습니다. 작년 기준으로 LCRQ는 가장 성능이 좋은 알고리즘으로 알려져 있습니다. LCRQ가 어떻게 동작하는지 살펴보겠습니다. Original LCRQ Paper Baseline & Simple approaches Reminder & notations 큐를 위해서는 enqueue(x)와 dequeue() -> x를 지원해야 합니다. Array-based queue에서는 enq는 tail을, deq는 head를 1씩 증가시킵니다. CAS, FAA, linearizability, correctness, Cell...
-
F-deletion 문제의 최적 알고리즘
1. 서론 지난 글에서는 $\mathcal{F}$-deletion 문제의 FPT(Fixed-parameter tractable) 알고리즘에 대해 살펴보았다. 해당 알고리즘은 treewidth가 $t$ 이하로 bounded인 그래프에서 $2^{2^{O(t \log t)}} n$ 시간에 동작하였다. $\mathcal{F}$-(M-)deletion 문제는 널리 믿어지는 Exponential Time Hypothesis 하에서 일반적인 그래프 클래스($\mathcal{F}$가 chair 및 banner로 불리는 작은 크기의 그래프의 contraction으로 나타낼 수 없는 연결 그래프를 포함하는 경우)에 대해 $2^{o(t \log t)} poly(n)$ 시간에 해결될 수 없음이 밝혀져 있다. 이 글에서는 2023년 논문 [1]에서 제시한 $2^{O(t \log t)} n$ 시간에 $\mathcal{F}$-(M-)deletion 문제를 해결하는...
-
Phase Transitions in Networks: Erdős–Rényi Model
0. Introduction 상전이(phase transition)는 물리학에서 나온 개념으로, 어떤 임계점을 기준으로 양쪽에서 행동이 달라지는 것을 말합니다. 물리학을 공부하는 경우 이러한 현상을 학습하게 되는데요, 대표적인 예시로 2차원 이징 모델이나 란다우 긴즈버그 모델 등이 있습니다. 놀랍게도 어떤 랜덤하게 구성한 네트워크들에 대해서도 이와 비슷한 상전이 현상이 일어남이 알려져 있습니다. 본 글에서는 그 중에서도 가장 간단한 모델인 Erdős–Rényi 모델에서 일어나는 상전이에 대해 공부해보려 합니다. 본 글은 KIAS-SNU Physics Winter Camp 2025 중 고등과학원 계산과학부 이덕선 교수님의 “Phase Transitions in Networks”...