<div id="readability-page-1" class="page"><div id="mArticle">
				<h2 id="dkBody">티스토리 뷰</h2>
				
				<div><p><a href="https://arxiv.org/pdf/2211.09606.pdf">https://arxiv.org/pdf/2211.09606.pdf</a></p>
<p>생각보다 내용이 많이 쉬워서 살짝 날먹이라고도 생각했다. 일단 핵심 내용은 다음과 같은 알고리즘의 존재성이다:</p>
<ul>
<li>$s, t$ flow가 $T$ 이하일때까지 $s, t$ flow를 incremental하게 관리하는 $O(Tm)$ 알고리즘이 존재한다.</li>
</ul>
<p>일단 이 알고리즘에 대해서 논의하기 전에, 이러한 알고리즘이 존재하면 어떻게 전체 문제를 해결할 수 있는지 살펴보자.</p>
<ul>
<li>플로우의 값이 $T$ 이하일 때까지는 $O(Tm)$ 알고리즘을 돌린다.</li>
<li>플로우의 값이 $T$ 를 넘어갔을 때는, 일단 플로우의 값이 $T$ 라고 하고 계속 간선 삽입 쿼리를 받자. 플로우의 값이 $T (1 + \epsilon)$ 을 넘어가면 위 값이 틀리게 된다. 이것이 일어나려면 최소 $T\epsilon$ 개의 간선이 추가되어야 하니, $T \epsilon$ 개의 간선이 추가되면 static maximum flow를 돌리고 답을 갱신해준다.</li>
</ul>
<p>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 를 계산하는 데에는 장점이 없다.</p>
<p>$O(Tm)$ 알고리즘을 다시 살펴보자. 플로우를 1 증가시키는 augmenting path가 존재한다는 것은 $s \rightarrow t$ 로 가는 residual directed path가 존재한다는 것과 동일하다. 고로 다음과 같은 쿼리 문제를 생각할 수 있다:</p>
<ul>
<li>방향 간선 추가</li>
<li>$s \rightarrow t$ 로 가는 경로를 찾으면 반환하고 종료</li>
</ul>
<p>만약에 이 쿼리 문제를 전체 $O(m)$ 시간에 해결할 수 있으면, 이제 augmenting path로 흘려주고 경로를 뒤집어준 후 다시 하면 되니까 문제가 해결된다. 이 쿼리 문제는 DFS를 하듯이 해결할 수 있다. 업데이트가 필요한 경우는 새 간선 $u \rightarrow v$ 에 대해 $s$ 에서 $u$ 는 방문 가능하고 $v$ 는 방문이 안 되는 경우인데, 이 간선이 추가되면 그냥 $v$ 에서 DFS를 돌려주면서 방문 가능한 정점을 추가로 체크해 주면 된다. 한번 방문한 정점을 두 번 이상 방문하지 않으니 DFS의 시간 복잡도가 선형인 것과 동일한 이유로 선형이다.</p></div>
				


				
			</div></div>

구사과

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의 시간 복잡도가 선형인 것과 동일한 이유로 선형이다.

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

댓글