구사과

그래프의 최대 독립 집합 문제는, 그래프가 주어졌을 때 최대 크기의 정점 부분집합 $S$를 골라서, $S$ 안에 있는 두 정점을 잇는 간선이 없게끔 하는 문제이다. 이 문제는 NP-complete임이 아주 잘 알려져 있다. 심지어 $O(n^{0.99})$-factor로 approximate할 수 있으면 $\textsf{NP} = \textsf{ZPP}$ 이다 (사실상 $\textsf{P} = \textsf{NP}$ 라는 뜻이다.) 어차피 제대로 못 푸는 문제이니 대신 다음과 같은 그리디 알고리즘을 생각해 볼 수 있다.순열 $\pi$ 를 잡고, 그 순서대로 정점을 순회한다. $\pi$ 는 모든 길이 $n$ 의 순열 중 랜덤하게 샘플.만약 현재 정점과 인접한 정점 중 $S$ 에 있는 정점이 없으면 현재 정점..

최대 차수가 $\Delta$ 인 그래프를 $(\Delta + 1)$ 개의 색으로 색칠하는 문제를 생각해 보자. 이 문제는 정점을 아무 순서로 보면서 남는 색을 배정해 주면 선형 시간에 쉽게 해결할 수 있다. 그러니 간선이 추가되고 삭제되는 쿼리를 넣어보자. 쿼리당 $O(\Delta)$ 시간에 문제를 해결하는 것은 쉽다:간선이 삭제되면 아무것도 하지 않는다.간선이 추가되었고, 만약 두 정점의 색이 다르다면, 한 정점에 대해서 남는 색을 배정해 준다. 남는 색을 찾아줘야 하기 때문에 $O(\Delta)$ 시간이 필요하다.더 빠른 알고리즘은 없을까? 이 문제를 처음 다룬 것은 내가 알기로는 Bhattacharya et al. 2018 이고, 당시에는 expected amortized $O(\log \Delta..

알고리즘을 모델링하는 여러 방법 중 하나는 Decision Tree이다. Decision Tree에서 알고리즘은 입력의 특정 부분을 읽어서 읽은 결과에 따라 YES / NO verdict를 결정하고, 비교 결과에 따라서 두 상태 중 하나로 분기한다. 예를 들어서 비교 정렬에서는 $x_i, x_j$ 를 읽은 다음에, $x_i - x_j$ 의 부호에 따라서 YES / NO verdict를 결정하고, 이 결과에 따라서 두 개의 자식 상태 중 하나로 분기한다.Decision Tree의 최대 깊이는 보통 알고리즘 시간 복잡도의 lower bound를 구성하는데 자주 쓰인다. 비교 정렬에서는 결과 상태가 최소 $n!$ 개이니, 최대 깊이가 적어도 $\log_2 (n!) = O(n \log n)$ 이고, 그래서 모든..