-
The number of topological sorts in DAG, AND polytope centroid
Introduction 문제를 풀다 보면 “조건을 만족하는 해 $x$를 찾아라” 라는 문제는 쉽게 풀 수 있지만, “조건을 만족하는 해 $x$의 개수를 찾아라” 라는 문제가 유독 어려운 경우가 많습니다. 대표적으로 2-SAT은 다항 시간 안에 해를 찾을 수 있지만, 2-SAT의 조건을 모두 만족하는 해의 개수를 찾는 것은 매우 어렵다는 것이 알려져 있습니다. 비슷하게 이분그래프의 완전 매칭은 다항 시간 안에 찾을 수 있지만, 완전 매칭의 개수를 구하는 것은 permanent라는 계산하기 어려운 식과 동치가 됩니다. 오늘 다룰 주제는 Directed Acyclic...
-
SAT problem의 변형과 Schaefer’s Dichotomy Theorem
Boolean Formula, SAT $(x \lor \neg y) \land (\neg x \lor z)$와 같은 식을 Boolean formula라 한다. Boolean formula의 변수(variable)는 True/False (또는 1/0이라고도 한다)의 두가지 값만을 가질 수 있다. 위 boolean formula의 variable은 $x, y, z$이다. 각 연산자에 대해 알아보면 $\lor$ 와 $\land$는 각각 logical OR(disjunction)/ logical AND (conjunction)를 나타내고, $\neg$(negation)는 NOT을 나타내는 연산자로 피연산자가 True였다면 False로, False였다면 True로 바꿔주는 역할을 한다. 식에서 각각의 항 $x, \neg y, \neg x, z$는 literal이라 한다. $x, y$와...
-
Karp의 21대 NP-완전 문제
Richard Karp는 알고리즘의 선두를 이끈 인물 중 한 명입니다. Problem solving을 하는 사람들에게는 Edmonds-Karp 최대 유량, Hopcroft-Karp 이분 매칭, Rabin-Karp 부분문자열 탐색 등으로 잘 알려져 있는데, 이 분의 업적으로 NP-완전성을 빼놓을 수 없습니다. 배경 지식 P, NP, 다항 시간 환원, 그리고 NP-완전 문제에 대해서는 koosaga님의 글 계산 복잡도 위계와 불리언 식의 “QBF 문제” 직전까지를 참조해 주시기 바랍니다. NP-완전 문제 1971년, Stephen Cook은 The complexity of theorem proving procedures 논문에서 “비결정적 튜링 기계로 다항 시간에 결정할...
-
Parametrized inapproximability for Steiner Orientation by Gap Amplification
Parametrized inapproximability for Steiner Orientation by Gap Amplification 이 글에서는 k-STEINER ORIENTATION 문제와 MAX (k, p)-DIRECTED MULTICUT 문제에 대한 FPT hardness result를 소개하는 논문을 정리한다. 먼저, k-STEINER ORIENTATION 문제는 다음과 같이 정의된다: 입력: mixed graph $G$ 와 $k$ 개의 terminal pair $T_G = {(s_1, t_1), (s_2, t_2), \ldots, (s_k, t_k)}$ (mixed graph 는 무방향 간선과 방향성 간선이 둘 다 존재할 수 있는 그래프를 뜻한다.) 출력: $G$ 의 모든 무방향 간선에 방향성을 주어서, $s_i \rightarrow t_i$...
-
FPT Inapproximability of Directed Multicut
FPT Inapproximability of Directed Multicut 그래프의 연결성, 그리고 연결성을 변화시키는 방법 (그래프 절단) 은 알고리즘 연구의 극초창기부터 연구되었던 문제들이다. 그래프 절단은 냉전 초기 공중폭격으로 적국의 철도망을 파괴하는 군사적인 목적으로 연구가 시작되었다. 이후 반세기 이상 이러한 류의 문제는 그래프에 대한 최적화 문제 중 가장 기초적인 문제로 자리잡는다. 이 문제는 이론적으로도 다른 문제의 근간이 되며, 무수히 많은 현실적 계산 문제와 연관되어 있다. 그래프 절단 유형의 문제로는 크게 다음과 같은 4가지 종류가 있다. 이하 특정한 언급 없을 시,...