Incremental approximate $s - t$ max flow in $m^{1/2+o(1)}$ update time

https://arxiv.org/pdf/2211.09606.pdf

생각보다 내용이 많이 쉬워서 살짝 날먹이라고도 생각했다. 일단 핵심 내용은 다음과 같은 알고리즘의 존재성이다:

• $s, t$ flow가 $T$ 이하일때까지 $s, t$ flow를 incremental하게 관리하는 $O(Tm)$ 알고리즘이 존재한다.

일단 이 알고리즘에 대해서 논의하기 전에, 이러한 알고리즘이 존재하면 어떻게 전체 문제를 해결할 수 있는지 살펴보자.

• 플로우의 값이 $T$ 이하일 때까지는 $O(Tm)$ 알고리즘을 돌린다.
• 플로우의 값이 $T$ 를 넘어갔을 때는, 일단 플로우의 값이 $T$ 라고 하고 계속 간선 삽입 쿼리를 받자. 플로우의 값이 $T (1 + \epsilon)$ 을 넘어가면 위 값이 틀리게 된다. 이것이 일어나려면 최소 $T\epsilon$ 개의 간선이 추가되어야 하니, $T \epsilon$ 개의 간선이 추가되면 static maximum flow를 돌리고 답을 갱신해준다.

static maximum flow의 시간 복잡도가 $O(m^{1+o(1)})$ 이니 $T = m^{1/2+o(1)} \epsilon^{-1/2}$ 을 설정해주면 전체 알고리즘이 $O(m^{3/2+o(1)} \epsilon^{-1/2})$ 시간에 작동함을 볼 수 있다. $\epsilon$ 에 대한 dependency도 sqrt인 점은 매력적이지만, exact max flow 를 계산하는 데에는 장점이 없다.

$O(Tm)$ 알고리즘을 다시 살펴보자. 플로우를 1 증가시키는 augmenting path가 존재한다는 것은 $s \rightarrow t$ 로 가는 residual directed path가 존재한다는 것과 동일하다. 고로 다음과 같은 쿼리 문제를 생각할 수 있다:

• 방향 간선 추가
• $s \rightarrow t$ 로 가는 경로를 찾으면 반환하고 종료

만약에 이 쿼리 문제를 전체 $O(m)$ 시간에 해결할 수 있으면, 이제 augmenting path로 흘려주고 경로를 뒤집어준 후 다시 하면 되니까 문제가 해결된다. 이 쿼리 문제는 DFS를 하듯이 해결할 수 있다. 업데이트가 필요한 경우는 새 간선 $u \rightarrow v$ 에 대해 $s$ 에서 $u$ 는 방문 가능하고 $v$ 는 방문이 안 되는 경우인데, 이 간선이 추가되면 그냥 $v$ 에서 DFS를 돌려주면서 방문 가능한 정점을 추가로 체크해 주면 된다. 한번 방문한 정점을 두 번 이상 방문하지 않으니 DFS의 시간 복잡도가 선형인 것과 동일한 이유로 선형이다.