Shortest Cycle Through Specified Elements

https://epubs.siam.org/doi/epdf/10.1137/1.9781611973099.139

Andreas Bjorklund는 그래프 이론에 대수적 방법을 접목시켜서 50년짜리 SOTA를 여럿 깬 것으로 유명하다. 최근에 논문 중 하나를 읽어볼 기회가 생겼는데 생각보다 훨씬 elementary한 방법이라서 놀랐다. 간단하게 요약하면 좋을 것 같아서 짧은 노트를 써 본다.

문제는 "그래프가 있고 K개의 정점이 마크되어 있을 때 이 정점들을 모두 지나는 최소 길이 simple cycle을 찾는 문제" 이고, 시간 복잡도 aim은 $O(2^k poly(N))$ 이다.

풀이는 다음과 같다. 먼저 찾을 사이클의 시작점을 $k$ 개 중 하나로 고정하자.

다음과 같은 walk $w = \{s, v_1, v_2, ..., v_{l-1}, s\}$ 를 good walk 라고 정의한다. walk임에 유의하자. simple할 필요는 없다.

• 고정한 시작점 $s$ 에서 시작함.
• $v_i$가 K개 정점 중 하나일 때 $v_{i-1} \neq v_{i + 1}$ (simple한 조건을 relax했다 생각)
• K개의 정점은 모두 정확히 한 번씩 방문함
• $v_1 < v_{l-1}$ (이건 별거 아님, double counting 방지)

Good walk의 개수 mod p는 DP를 사용하여 $O(poly(N) * 2^K)$ 에 찾을 수 있다. 일단 한동안은 $p = 2$라고 하자.

여기서 다음과 같은 사실을 증명할 수 있는데, 최적해의 길이를 $l$ 이라고 하자. 길이 $l$ 의 Good walk의 개수 mod 2는, 길이 $l$ 의 모든 정점을 지나는 simple cycle (good simple cycle?) 의 개수 mod 2와 동일하다.

이를 증명하기 위해서는, simple하지 않은 good walk들 간에 Matching을 찾아주면 될 것이다.

Good walk이며 Good cycle이 아닌 경우를 보자. 사이클이 아니기 때문에 두번 이상 방문하는 정점이 있다. 이 정점은 K개의 정점에 속하지 않을 것이고, 이 정점이 처음 등장하는 위치를 $v_i$, 가장 마지막 등장하는 위치를 $v_j$ 라고 하자.

• 만약 $v_i \ldots v_j$구간이 팰린드롬이 아니면, 그냥 요걸 뒤집으면 다른 Good walk를 또 하나 얻는다. 그래서 mod 2로 contribution이 0이 되어서 깔끔하게 해결된다.
• 그렇지 않은 경우가 신기하다. 일단 팰린드롬의 길이(=경로길이+1)은 무조건 홀수여야 함을 상기하자 (아닐 경우 셀프 루프가 존재한다는 뜻임). 짝수일 경우 중앙 정점을 기준으로 v_{i-1}, v_{i + 1} 이 동일하다. 그렇다면 Good walk의 성질에 의해서 중앙 정점은 K개의 정점이 아니고... 그냥 지워주면 된다. 그래서 이런 경우는 더 짧은 사이클을 얻을 수 있다.

이제 이걸 실제 랜덤 알고리즘으로 만들기 위해서는, mod 2 대신 그냥 적당히 큰 2^k 크기의 Finite field를 써 주면 되고, 각각의 간선에 random edge weight를 준 후, 경로 합이 아닌 경로 상 edge weight의 곱의 합을 구하는 식으로 DP를 변형시키면 된다. 그러면 x+x=0 은 만족하면서도, Good walk의 합들이 Zero가 될 가능성은 아주 적어진다.