-
Happy ending problem
서론 Extremal Graph Theory의 핵심 질문은 “무질서해 보이는 구조가 충분히 크다면, 그 안에 특정한 패턴이 필연적으로 존재하는가?”이다. 본 글에서는 이러한 ‘필연적 질서’에 대한 논의를 1차원 수열에서 시작하여 2차원 기하 영역으로 확장한다. 구체적으로 Erdős-Szekeres Theorem을 통해 수열에서의 단조 부분 수열의 존재성을 증명하고, 이를 일반화하여 평면 기하학의 난제 중 하나였던 Happy Ending Problem과 볼록 다각형의 존재성에 대한 상한과 하한을 논한다. 1. Erdős-Szekeres Theorem Extremal Graph Theory의 논의를 시작하기 위해, 가장 기초적이면서도 강력한 정리를 소개한다. 이는 1차원 수열...
-
K-Center Problem in Tree
1. Introduction k-center problem은 그래프에서 $k$개의 센터를 선택하여 모든 정점으로부터 가장 가까운 센터까지의 거리의 최댓값을 최소화하는 최적화 문제입니다. 이는 도시 내에 소방서나 응급 의료 센터와 같은 필수 시설을 배치할 때, 가장 가까운 시설까지의 거리가 일정 수준을 넘지 않도록 해야 하는 상황에서 주로 사용됩니다. 일반 그래프에서의 k-center problem은 NP-hard로 알려져 있으며, $P \neq NP$ 가정 하에 2-approximation보다 나은 근사 알고리즘 또한 NP-hard임이 증명되어 있습니다. 때문에 일반 그래프에서는 근사 알고리즘을 이용한 접근이나, 그래프의 특수한 구조를 이용하는 접근이...
-
Parallel Small Vertex Connectivity In Near-Linear Work and Polylogarithmic Depth
Introduction 이 글에서는 제가 Yonggang Jiang과의 공동 연구로 작성한 논문에서 다룬 문제인 k-vertex connectivity의 효율적인 병렬 알고리즘에 대해 설명합니다. 최근 유명한 그래프 문제들을 병렬/분산 환경에서 해결하는 연구에 많은 진전이 있었는데, 이 글을 통해 다양한 계산 모델에서 효율적인 알고리즘을 설계할 때 어떤 관점이 유용한지 제 나름의 직관을 풀어보고자 합니다. Preliminary 무방향, 무가중치 그래프 $G$가 주어졌을 때, $V(G)$의 분할 $(L, S, R)$이 $L, R \neq \emptyset$이고, $L$과 $R$ 사이에 간선이 없으면 이를 Vertex Cut이라고 합니다. 이때 가능한...
-
F-deletion 문제의 FPT 알고리즘
Introduction NP-hard로 분류되는 여러 그래프 관련 문제들을 아래와 같이 다른 관점에서 살펴보자. Vertex Cover Vertex Cover란 모든 간선의 최소 하나의 끝점을 포함하도록 하는 최소 크기의 vertex subset(minimum size vertex cover)을 찾는 문제이다. 이는, 다르게 생각하면 그래프에서 최소 개수의 정점을 제거하여, 그래프의 간선이 없도록 만드는 문제와 같다. 즉, $G$가 $\newcommand{\F}{\mathcal{F}}\mathcal{F} = {K_2}$ 를 minor로 포함하지 않도록 하는 것과 동치이다. Feedback Vertex Set Feedback Vertex Set 문제는 그래프에서 최소 개수의 정점을 제거하여 cycle을 포함하지 않도록 하는 문제이다....
-
Tensor Network
텐서 네트워크(Tensor Network Diagram)는 양자 컴퓨팅, 인공지능에 이르기까지 다양한 분야에서 활용되는 강력한 수학적 도구입니다. 복잡해 보이는 텐서 연산을 쉽게 하기 위해서는 다양한 트릭들이 필요한데, 텐서 네트워크는 텐서간의 연산을 그래프로 표현해서 복잡한 연산을 간단하고 직관적으로 다룰 수 있게 해줍니다. 이번 포스트에서는 텐서 네트워크 중에서도 양자 컴퓨팅에 자주 쓰이는 부분들을 소개하고자 합니다. 내용은 참고문헌 [1]을 주로 참고하였습니다. Quick Review: Bra-Ket Notation 우선 기본적인 bra-ket 표기법은 간략하게만 복습하고 넘어가겠습니다. bra-ket 표기법은 Paul Dira이 1939년에 제안한 표기법으로, 양자 상태를...