이 글은 GPT 4.5가 최종 편집하였다. 썸네일 역시 GPT로 생성했지만, 본문의 내용과는 아무 관련이 없다.그래프의 Vertex Ranking은 다음 조건을 만족하는 labeling $\rho : V \to \mathbb{Z}_{\ge 1}$로 정의된다.서로 다른 두 정점 $u, v$에 대해서 $\rho(u) = \rho(v)$라면, 이들을 연결하는 모든 경로상에 항상 $\rho(x) > \rho(u)$를 만족하는 정점 $x$가 존재해야 한다.이때 $\rho(v)$의 최댓값을 vertex ranking number 또는 vertex ranking chromatic number $\chi_{vr}(G)$라고 부른다. 당연히 일반적인 chromatic number보다는 크거나 같다. 트리에 대해서는 비교..

이 글은 GPT-4.5가 최종 편집하였다. 썸네일의 suffix array도 GPT가 그렸지만, 아쉽게도 틀렸다.길이가 $n$인 문자열 $S$의 접미사 배열(Suffix Array, SA)이란, $S$의 모든 접미사(suffix) $S[i\dots]$들을 사전 순으로 정렬했을 때의 시작 인덱스 순열을 말한다. 예를 들어, $S = aba$라면 접미사들을 사전 순으로 정렬했을 때 $a koosaga님의 글을 참고하면 좋다.Inverse Problem어떤 순열 $\sigma$가 주어졌을 때, 이를 접미사 배열로 하는 문자열은 몇 개나 존재할까? SA는 $S[\sigma(0)] \le \dots \le S[\sigma(n-1)]$라는 관계를 나타내므로, 우리는 이 등호가 언제 성립하지 않는지만 판별하면 된다...

Problem statement정점 $n$개인 무방향 그래프 $G$가 주어진다. 정점이 $k$개인 path $P_k$와의 cartesian product $G \square P_{k}$의 cartesian product의 스패닝 트리의 개수를 구하여라. $n \le 500$, $k \le 10^{18}$.Matrix-tree theorem그래프 $G$의 Laplacian 을 $L_{G} := D_{G} - A_{G}$로 쓰자. $L_{G}$는 real symmetric matrix이고, positive semidefinite이므로 양의 실수 고윳값을 갖는다. Connected graph $G$에 대해 $L_{G}$는 rank $n-1$이 되는데, non-zero eigenvalue를 $\lambda_{1..

Correlation clustering은 그래프의 정점들을 cluster들로 분할하는데, 각 간선 $e$에는 두 종류의 weight $w_{e}^{+}$와 $w_{e}^{-}$가 있다. 두 endpoint가 같은 cluster에 있으면 $w_{e}^{+}$점, 다른 cluster에 있으면 $w_{e}^{-}$점을 얻는다. 목표는 점수의 합을 최대화하는 clustering을 찾는 것이다. 이 문제는 NP-hard임이 알려져 있고, Max cut처럼 SDP를 이용한 constant factor approximation이 알려져 있다.이번에도 직관적인 $0.5$-approximation이 있는데, 모든 정점을 한 cluster에 놓거나 / 정점을 다 다른 cluster에 두거나 둘 중 나은 것이 최적해의 절..

https://www.acmicpc.net/problem/25510https://infossm.github.io/blog/2022/08/18/CharPoly/Division-Free Determinant에 대해 위 문제를 내고 글도 썼는데, 최근 훨씬 간단한 알고리즘이 있다고 해서 정리해보려고 한다.원본 글에 달린 것과 동일하게 $\mathcal{O}(n^4)$에 동작하는 division-free characteristic polynomial 알고리즘이다.Algorithm$n \times n$ 행렬 $A = (a_{ij})$에 대해, $A_{i}$를 $i\dots n$번째 행, 열만 따와서 만든 크기 $n-i+1$의 정사각행렬이라고 하자. 당연히 $A_{1} = A$이다.$p_{1}(x) = \det(x..

Lindström–Gessel–Viennot lemma는 DAG의 non-intersecting path를 셀 때 사용할 수 있는 공식이다.$G = (V, E)$에서 $2n$개의 정점 $a_{1}, \cdots, a_{n}$, $b_{1}, \cdots, b_{n}$을 생각하자. 어떤 두 path가 intersecting하다는 것은 둘 사이에 공통된 정점이 있다는 것이다. path tuple $P = (P_{1}, \cdots, P_{n})$에 대해 $P_{i}$가 $a_{i}$를 $b_{\sigma(i)}$로 보내고, $\sigma$가 순열이면 이러한 $P$를 path system이라고 하자. $P$가 non-intersecting이면 non-intersecting path system이라고 부르고, ..

https://www.acmicpc.net/problem/21268솔루션에서 Tellegen's Principle을 인용하고 있어서 지난 포스트와 연관해 작성해본다. 머리 좋은 사람들은 아마 생각하지 않고도 풀 수 있을 것 같다.Without Tellegen's principle$E_{k} = \sum_{i = 1}^{n} C_{i} \prod_{j = 1}^{k} (A_{i} + B_{j})$를 답이라고 하자.$i$와 관련한 항들을 사부작거리다보면, $P_{j} = \sum_{i = 1}^{n} C_{i}A_{i}^{j}$를 미리 계산해두면 편할 것 같다.$\sum_{j} F_{k, j}x^{j} = (x+B_1)(x+B_2)\cdots (x+B_{k})$라고 두면, $E_{k} = \sum_{j} P..

오늘 다룰 Max Cut 문제는 non-negative weighted undirected graph $G = (V, E, w)$에 대해서 $S \subseteq V$를 골라서 $vE(S, V - S)$의 weight 합을 최대화하는 문제이다. 다항 시간 알고리즘이 알려진 min cut에 비해 이 문제는 NP-hard임이 알려져 있다.NP-hard problem의 경우 여러 근사 알고리즘들이 존재하는데, 가장 naive한 알고리즘부터 생각해보자. 임의의 $S \subseteq V$에 대해 $E(S, V-S)$의 weight 합, 즉 $\sum_{e \in E(S, V-S)} w(e)$를 $w(\partial S)$라고 표기하자. $w(\partial S)$의 가능한 최댓값, 즉 MAX CUT을 $\mat..