2026년 2월 4일

최소 버텍스 커버

1. Kőnig's theorem In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.
2. 이분 그래프에 대해 최대 매칭 = 최소 버텍스 커버 = 최대 유량 = 최소 컷 이다.
3. 이분 그래프에서 최소 버텍스 커버를 $C$라고 할 때 최대 독립 집합 $S$는 $V\setminus C$이다.
4. 이분 그래프 네트워크에서 min cut을 구하고 cut edge와 연결된 정점을 색칠하면 이는 최소 버텍스 커버이다.

4에 대한 간단한 증명. source 또는 sink와 연결된 간선의 용량은 $1$이고 나머지 간선의 용량은 $\infty$ 이므로 cut edge는 source 또는 sink와 연결되어 있다. 색칠한 정점의 집합이 버텍스 커버가 아니라고 하자. 그렇다면 정점 $u$와 정점 $v$가 모두 색칠되지 않은 간선 $uv$가 존재한다. 경로 $s\rightarrow u \rightarrow v \rightarrow t$가 존재하므로 모순이다. 따라서 색칠한 정점의 집합은 버텍스 커버이고 크기가 min cut과 같으므로 이는 최소 버텍스 커버이다.

AtCoder Regular Contest 213 (Div. 1)

A - Swapping Game

$N$개의 정점이 있고 정점 $i$는 가중치 $C_i$와 길이가 $L$인 순열 $P_i$를 가지고 있다. 정점 $i$, $j$가 $i < j$, $\text{dist}(P_i, P_j) \le j - i$를 만족하면 $i$에서 $j$로 이동 가능하다. 이때 두 순열 사이의 거리는 Kendall tau distance로 정의된다. 변환 $b_i \rightarrow i$를 $a$에 적용한 순열을 $a'$이라고 하자. $\text{dist}(a, b)$는 bubble sort로 $a'$를 오름차순으로 정렬할 때의 swap 횟수이고 inversion의 합과 같다. $\text{dist}(P_i, P_j)$를 $O(L)$에 계산하면 $O(N^2L)$ DP로 답을 구할 수 있다. $\text{dist}(a, b) \le \binom{L}{2}$라는 사실을 이용하면 $O(NL^3)$으로 최적화할 수 있다.

B - Hamming Distance is not 1

Hypercube graph에서 구간 $[L, R]$에 포함되는 정점으로 구성된 부분 그래프 $G$의 최대 독립 집합을 구하는 문제이다. Hypercube graph는 이분 그래프이므로 최소 버텍스 커버를 찾자. $\text{popcount}(u) \equiv 0 \pmod 2$인 정점 $u \in G$의 집합을 $V_\text{even}$, $\text{popcount}(u) \equiv 1 \pmod 2$인 정점 $u \in G$의 집합을 $V_\text{odd}$라고 하자. $(2k, 2k+1)$를 매칭한 네트워크 그래프 $G'$을 생각하면 $G'$에 흐르는 유량은 최대 유량이거나 최대 $1$만큼 유량을 추가할 수 있다.

Case 1: $L \equiv 1 \pmod 2$, $R \equiv 0 \pmod 2$, $\text{popcount}(u) \not\equiv \text{popcount}(v) \pmod 2$, $L \oplus 2^{\lfloor \log_2{(L \oplus R)}\rfloor} \le R$

유량을 $1$만큼 추가할 수 있다. 완전 매칭이므로 $V_\text{even}$과 $V_\text{odd}$는 최소 버텍스 커버이다.

Case 2: $L \equiv 1 \pmod 2$, $R \equiv 0 \pmod 2$, $\text{popcount}(u) \not\equiv \text{popcount}(v) \pmod 2$, $L \oplus 2^{\lfloor \log_2{(L \oplus R)}\rfloor} > R$

유량을 추가할 수 없다. Residual network를 탐색해서 최소 버텍스 커버를 찾을 수 있다.

Case 3: Case 1 또는 Case 2에 해당하지 않는 경우

유량을 추가할 수 없다. $V_\text{even}$과 $V_\text{odd}$중에서 크기가 $\min(|V_\text{even}|, |V_\text{odd}|)$인 집합은 최소 버텍스 커버이다.