Karp의 최소 사이클 평균 가중치 알고리즘

문제

방향과 가중치가 있는 그래프 $G = (V, E, w: E \rightarrow \mathbb{R})$가 있습니다. 여기서 사이클의 평균 가중치란 사이클을 구성하는 간선 가중치의 평균을 의미합니다. 그래프 $G$에 있는 모든 사이클 중 제일 작은 평균 가중치인 최소 사이클 평균 가중치는 무엇일까요? 엄밀히 작성하면 다음과 같습니다.

• 사이클이란 정점의 수열 $c = e_1, e_2, \cdots, e_k$을 의미하며, 다음 조건을 만족해야합니다.
  • $e_i$의 끝 정점은 $e_{i+1}$의 시작 정점이어야 하며, $e_1$의 시작 정점과 $e_k$의 끝 정점은 같아야 합니다.
• 사이클 $c = e_1, e_2, \cdots, e_k$의 평균 가중치 $\mu(c)$는 다음과 같이 정의됩니다.
  • $\mu_G(c) = \frac{1}{k} \sum_{i=1}^k w(e_i)$
• 우리가 찾으려는 것은 그래프 $G$에 존재하는 모든 사이클 $c$에 대해 $\mu(c)$의 최솟값인 $\mu_G^* = \min_{c: \mathrm{\ cycle\ of\ }G} \mu_G(c)$ 입니다.

O(VE log(VW)) 알고리즘

$G$에 음수 가중치 사이클이 있으면, $\mu^*_G < 0$입니다. $\frac{1}{k}$는 부호에 영향을 주지 않습니다.

$G$에 있는 간선의 가중치를 전부다 $\alpha$씩 뺀 $G' = (V, E, w')$이 있다고 합시다($즉, w'(e) = w(e) - \alpha$입니다.) 이 때, 최소 사이클 평균 가중치도 $\alpha$만큼 줄어듭니다.

증명

• $\mu_{G'}(c) = \frac{1}{k} \sum_{i=1}^k w'(e_i)$ $= \frac{1}{k} \sum_{i=1}^k (w(e_i) - \alpha) = (\frac{1}{k} \sum_{i=1}^k w(e_i)) - \alpha = \mu_G(c) - \alpha $입니다.
• 그러므로 $\mu_{G'}^* = \min_{c: \mathrm{\ cycle\ of\ }G'} \mu_{G'}(c) = \min_{c: \mathrm{\ cycle\ of\ }G} (\mu_{G}(c) - \alpha) = \mu^*_G - \alpha$입니다.

이 Idea를 이용하면 다음과 같은 풀이를 찾을 수 있습니다.

• 가중치가 $\alpha$보다 큰지 판단하기 위해서는, 모든 간선의 가중치에 $\alpha$를 뺀 그래프에서 음수사이클이 있는지 확인하면 됩니다.
• 음수 사이클이 있는지 확인하는 시간복잡도는 Bellman-Ford등의 알고리즘을 활용하면 $O(VE)$시간에 구할 수 있습니다.
• 총 시간복잡도는 $O(VE \log (VW))$ 정도입니다.

O(VE) 알고리즘

Bellman Ford는 길이 정보를 저장하지만 길이가 어떤 $k$이하라는 것만 저장하지 해당 길이에 대한 정확한 정보를 주지 않습니다. 그렇기 때문에, 우리는 길이 정보를 추가적으로 저장합니다.

$\delta_G^k(v)$를 길이가 정확히 $k$이고 정점 $v$에서 끝나는 모든 경로의 길이 중 최솟값이라고 합니다. 특히, $\delta_G^0(v)$ 는 모든 $v$에 대해 $0$입니다. 또한 $\delta_G^*(v)$를 $\delta_G^k(v)$중 최솟값이라고 합시다. 어떤 그래프가 $\mu_G^* = 0$인 경우, 다음과 같은 성질이 성립합니다.

• 모든 $v$에 대해 $\delta_G^k(v) = \delta_G^{*}(v)$인 $0 \le k < \lvert V \rvert$가 존재합니다.
  • $v$로 오는 길이 $\lvert V \rvert$ 이상의 경로는 $\lvert V \rvert+1$개 이상의 정점을 방문해야 하며, 같은 정점을 두 번 방문 합니다. 같은 정점을 두 번 방문하는 사이클을 경로에서 제외한 경로는 더 짧고 가중치가 작거나 같습니다(사이클의 길이는 0 이상입니다.) 이 방법으로 사이클이 없을 때 까지 경로를 줄일 수 있으며, 사이클이 없는 경우 $k < \lvert V \rvert$입니다.
• $\delta_G^{\lvert V \rvert}(v) \le \delta_G^{*}(v)$ 인 $v$가 존재합니다. 즉, $\min_{v \in V} \left( \delta_G^{\lvert V \rvert} (v) - \delta_G^{*}(v) \right)= 0$입니다.
  • 길이가 $0$인 사이클의 정점이 차례대로 $v_1, \cdots, v_k$라고 합시다. 또한 편의상, $v_{k+x} = v_x$라고 합시다. 다음의 보조정리를 증명합시다.
  • $v_i$에서 $v_{i+1}$로 가는 간선 가중치가 $w$이면, $v_{i+1}$에서 $v_i$로 가는 최단경로는 $-w$입니다.
    • 사이클에 속한 간선 가중치 합은 $0$이기 때문에 나머지 간선들의 가중치 합은 $-w$입니다. 이보다 더 가중치가 낮은 경로가 존재하면 음수 사이클이 됩니다.
  • $v_i$에서 끝나는 경로 중 가중치 합이 가장 작은 경로의 길이가 $l$이라고 합시다. 그러면 $v_{i+1}$에서 끝나는 경로 중 경로 가중치 합이 가장 작은 길이 $l+1$의 경로가 있습니다.
    • $v_i$에서 $v_{i+1}$로 가는 간선을 추가하면 됩니다. 만약 이보다 작은 최단경로가 존재한다면, $v_{i+1}$에서 $v_i$까지 사이클을 따라 가면, $v_i$에서 끝나는 가중치 합이 더 작은 경로가 있어서 모순입니다.
  • $v_1$까지 가는 최소 가중치 경로의 길이가 $l$이면, 사이클을 $\lvert V \rvert -l$번 더 타고 간 $v_{1+\lvert V \rvert -l}$번 정점에 대해 성립합니다.

이제 $\delta_G^{\lvert V \rvert} (v) - \delta_G^*(v)$라는 식을 $\max_{0 \le k < \lvert V \rvert} \left( \delta_G^{\lvert V \rvert}(v) - \delta_G^k(v) \right)$로 풀어 씁시다. 이후 경로에 대한 다음 관찰을 이용합시다.

• $G$의 간선 가중치를 $\alpha$씩 뺀 $G'$에 대해 $\delta_{G'}^{n} = \delta_{G}^{n} - n \alpha$입니다.
  • $G'$에서의 경로는 $G$에서의 경로와 같으며, 간선을 총 $n$개 방문했고 각 가중치는 $\alpha$작으므로 총 $n\alpha$작습니다.

이제 $\delta_{G'}^{\lvert V \rvert}(v) - \delta_{G'}^k(v) = \delta_G^{\lvert V \rvert}(v) - \delta_G^k(v) - (\lvert V \rvert - k) \alpha$라는 것을 알 수 있고, 경로의 길이에 상관 없이 $\alpha$만 남기 위해서는 양변에 $\lvert V \rvert - k$를 나눠주면 됩니다. $\max_{0 \le k < \lvert V \rvert} \left( \delta_G^{\lvert V \rvert}(v) - \delta_G^k(v) \right)$ 는 항상 $0$ 이상이고, $0$인 $v$가 존재하므로, $F(G) = \min_{v \in V}  \max_{0 \le k < \lvert V \rvert} \left( \dfrac{ \delta_G^{\lvert V \rvert}(v) - \delta_G^k(v)}{\lvert V\rvert - k} \right)$에 대해서도 마찬가지입니다. 여기서 가장 중요한 점은 모든 간선 가중치에 $\alpha$를 빼면 이 값이 $\alpha$가 줄어드는, 즉, $F(G) = F(G') - \alpha$가 성립한다는 점입니다. $\mu^*_{G'} = 0$인 $G'$에 대해서 $F(G') = 0$이므로, $\mu^*_G = \alpha$인 $G$에 대해서는 $F(G) = \alpha$가 성립합니다.

 

결론적으로 $G$의 최소 사이클 평균 가중치는 $F(G) = \min_{v \in V} \max_{0 \le k < \lvert V \rvert} \left( \dfrac{ \delta_{G}^{\lvert V \rvert}(v) - \delta_{G}^k(v)}{\lvert V\rvert - k} \right)$로 구할 수 있으며, $\delta_G^0 (v) = 0;$ $\delta_G^i (v) = \min_{u \rightarrow v \in V} \left( \delta_G^{i-1} (u) + w( u \rightarrow v) \right)$를 이용하면 $O(VE)$ 시간에 위 식을 계산할 수 있습니다.

문제 / 구현 / 참고 문헌

문제: https://acmicpc.net/problem/14747

구현: https://www.acmicpc.net/source/share/3a6b1c18811b46b591c503c7a98c62d9

참고 문헌

Richard M. Karp, A characterization of the minimum cycle mean in a digraph (1978), https://doi.org/10.1016/0012-365X(78)90011-0

https://courses.csail.mit.edu/6.046/fall01/handouts/ps9sol.pdf