Circulation

목표

• Circulation 문제를 Max Flow(혹은 Min Cost Flow) 문제로 환원시킬 수 있음을 이해한다.

Circulation이란

Definition

• 주어진 flow graph $G(V, E)$에 대하여,
  • $l(a, b)$: $a$에서 $b$로 가는 flow의 lower bound,
  • $u(a, b)$: $a$에서 $b$로 가는 flow의 upper bound,
• $l(a,b) \le f(a,b) \le g(a,b)$를 만족하고
• $inflow(x) - outflow(x) = \sum\limits_{(v, x) \in E} f(v, x) - \sum\limits_{(x, v) \in E} f(x, v) = 0$을 만족한다.
• $src$와 $sink$가 정의되지 않았음에 유의하라.

Min cost Circulation

• 위 간선들에 대해 $c(a, b)$: $a$에서 $b$로 가는 flow의 unit flow 당 cost
• minimize $\sum\limits_{(a,b)\in E} f(a,b)\cdot c(a,b)$

Multi-commodity Circulation

• multi (source-sink) pair로도 생각할 수 있다.
• 각 간선 별로 commodity(종류)가 여러개 있어서, 자원(cap)을 함께 공유하고,
• commodity에 대해서도 lower bound가 존재한다
• $f(a,b) = \sum\limits_{i} f_{i}(a,b)$
• $l_{i}(a,b) \le f_{i}(a,b)$

Source와 Sink를 가진 Flow Graph를 Circulation으로 변환

• 일반적인 Flow Graph는 Source와 Sink를 가진다.
• 어떤 정점의 net flow를 $f(v)=inflow(v)-outflow(v)$라 정의하자.
• 그러면 $f(src) \le 0, \ f(sink) \ge 0, \ f(src) = -f(sink), \ \forall v \in V\setminus {src, sink}:\ f(v)=0$을 만족해야 한다.
• Flow Graph를 조금 더 일반화해보자.
  • $src, sink$만 예외처리해주는게 마음에 안 든다.
  • 모든 정점에 대해 $f(v)=0$으로 만들 수 있을까?
• 만약 $demand(v)$라는 것이 있어, $f(v) = demand(v)$를 만족하는 flow만이 feasible flow가 된다고 생각해보자.
  • 위 예시는 $src$, $sink$를 제외하고 모두 $demand(v)=0$이다.
  • 기존 $src$와 $sink$의 경우 단순히 $f(src)=-f(sink) \le 0$만 만족하면 되므로 난해하다.
  • 이는 사실 $f(src) = -outflow(src), f(sink) = inflow(sink)$이므로 그런것이므로,
  • $inflow(sink)-outflow(src)=f(sink)+f(src)=0$
  • 이는 $sink$에서 $src$로 가는 $cap=\infty$인 간선을 추가해주는 것으로, $outflow(src) = inflow(sink) = outflow(sink) = inflow(sink)$를 만족시키게 할 수 있다.
  • 즉, $demand(src)=demand(sink)=0$으로 두어도 충분하다.
• 이때 당연히 $\sum\limits demand(v) \neq 0$인 경우 feasible flow가 없다.
  • 이 경우 $\sum\limits demand(v)$의 부호에 따라 dummy vertex를 만들어서 redundant한 demand를 수용할 수 있도록 연결해주면 된다.
• 이러한 모델링은 일반적으로 Flow Network를 LP(Linear Programming)로 모델링하기 위해 사용된다.
• $src$와 $sink$를 제외하고 모든 $demand(v)=0$일 경우에 이 변환을 수행하면 Circulation 문제가 된다.
  • 아무 Flow를 흘리지 않는 것이 가능한 해다.

Circulation의 해결

Flow Graph를 Circulation Graph로 변환

• Circulation은 $\forall x\in V, \ demand(x)=0$으로 정의되어 있어야 함을 알 수 있다.
• 다음과 같은 경우들에도
  • $src, sink$가 존재하여 $demand(x)$가 정의되지 않았거나,
  • $demand(x) \neq 0$인 $x$가 존재하거나,
  • $\sum\limits demand(x) \neq 0$인 경우에도 (사실 이는 feasible solution이 존재할 수 없지만 최대한 비슷한 해를 찾는다)
• 그래프를 재건축하여 모든 $demand(x) = 0$이 되도록 할 수 있다.
• Case 1: $src$와 $sink$가 있는 일반적인 flow 그래프인 경우
  • $u(sink, src) = \infty$간선을 추가하여 $demand(src)=demand(sink)=0$으로 정의한다. (사실 이 간선에 흘려진 플로우가, $src \rightarrow sink$ 플로우와 동일하다)
• Case 2: $demand(x)$가 모든 정점에 대해 정의되었으나, $\exists x \ demand(x) \neq 0$이고 $\sum\limits demand(x)=0$인 경우
  • global source와 global sink를 정의하여
  • global source에서 $demand(x)<0$인 점 $u(gsrc, x)=-demand(x)$으로 간선을 잇고
  • $demand(x) > 0$인 점에서 global sink로 $u(x, gsink)=demand(x)$으로 간선을 이어주면
  • 일반적인 source와 sink가 있는 flow graph로 변환할 수 있다.
  • 이때 처음에 $\sum\limits demand(x) \neq 0$인 경우에도, $src \rightarrow sink$ max flow를 구했을 때 $\sum\limits_{demand(x)>0}{demand(x)}$와 같은 경우 feasible solution이 존재한다.
  • Case 1으로 돌아가서 그래프를 변환한다.
• Case 3: $\sum\limits demand(x) \neq 0$인 경우
  • dummy node를 만들어서 demand를 $-\sum\limits demand(x)$로 부여한다.
  • $\sum\limits demand(x) > 0$인 경우
    • dummy node로부터 $demand(x) > 0$인 점들에게 각각 cap $\infty$ 간선을 잇는다.
  • $\sum\limits demand(x) < 0$인 경우
    • $demand(x) < 0$인 점으로부터 dummynode에게 각각 cap $\infty$ 간선을 잇는다.
  • 이제 이 그래프는 feasible solution이 존재한다.
  • Case 2로 돌아가서 그래프를 변환한다.
• 따라서 flow 정보를 유지하면서, 모든 정점의 $demand(x)=0$으로 바뀐 그래프를 만들 수 있다.

Circulation 알고리즘

• 현재 문제는 간선에 flow의 하한이 있다는 것이다.
• $l(a, b) \le f(a,b) \le u(a,b)$가 주어질 때
• 이를 $a$에 $l$의 유량이 들어올 때, 이를 $(a,b)$ 간선에 흘리도록 강제한다고 생각할 수 있다.
• 그러면 다시 $demand(a)$의 개념을 도입하면
• $demand(a)$를 $l(a,b)$만큼 증가시키고, $demand(b)$를 $l(a,b)$만큼 감소시켜서 $(a,b)$ 간선에 $l(a,b)$의 유량이 흐르도록 강제하자(유량을 미리 확보하는 느낌).
• 그러면 이 간선은 $0 \le f'(a,b) \le u(a,b)-l(a,b)$ 이라는, 새로운 하한과 상한을 가지게 된다.
• 모든 간선에 대해 이 작업을 해주면 각 정점에는 변화한 $demand(x)$가 생긴다.
• 이제 아까의 Graph 변환 테크닉의 Case 2로 돌아가자. global source, global sink를 세팅하여 src, sink Flow Graph로 변환할 수 있고다.
• 여기서 Flow를 찾는 것은 기존 그래프의 Flow와 서로 변환 가능하다.
• 유의할 것은 이 그래프에서 구한 Max Flow가 positive demand sum과 같은 경우만 Feasible Flow라는 것이다.
• 각 간선의 flow에 $l(a,b)$를 더해주면 실제 flow 값을 구할 수 있다.
• 이 경우 Dinic의 시간복잡도와 같다.
• $O(EV^{2})$

Max Flow Circulation

• Circulation을 모두 구한 상태의 그래프를 생각해보자.
• 이 Residual Graph에서, $sink \rightarrow src$ 간선에 흐르는 Flow가 현재 Flow일 것이다. 이 값을 $X$라 하자.
• Residual Graph에서 $src$에서 $sink$로 새롭게 Max Flow를 구해준다.
• $X$에 새롭게 구한 Flow를 더해주면 답이 된다.
• 이 알고리즘이 정당한 이유는 더 이상 Cycle Canceling을 통해 플로우를 흘릴 수 없는 경우 Global Maximum Flow인 것이 증명되었기 때문이다.
• (출처: https://koosaga.com/134)

Fixed Flow Circulation

• $sink$에서 $src$로 간선을 연결할 때 Cap을 $X$라고 두자. 그러면 $src$에서 $sink$로 흐르는 유량이 $X$로 제한된다.
• Circulation을 찾은 뒤 이 간선의 flow 값을 체크해주면 된다.

Min Flow Circulation

• 이때 feasible flow가 존재하는 $X$의 최솟값을 찾으면 된다.
• Monotocity가 있으므로 Binary Search를 할 수 있다.
• $\log F$ 항이 추가로 붙는 것.

Circulation with Cost

• Dinic 대신 MCMF를 돌리거나, 애초에 다른 모델링을 시도할 수 있다.
• 사실 Circulation은 Cost가 있든, 없든 간선에 Cost를 부여하여 MCMF로 풀 수 있다.
• $l(a,b)>0$인 각 $(a,b)$ 간선에 대해서 cap: $l(a,b)$, cost: $-1$인 간선과 cap: $u(a,b)-l(a,b)$, cost: $0$인 간선 2개로 분리하자.
  • Circulation with Cost의 경우 cost를 각각 $-INF + c(a,b)$, $c(a,b)$로 두면 된다.
• 기존 MCMF를 돌려주면 cost의 합의 negation이 위 간선 수와 같은지 확인해주면 된다. 이때 flow의 최솟값은 Binary Search을 해도 되고, flow를 흘릴 때 cost가 0이상이 된 순간에 끊는 방식으로도 가능하다.
  • Circulation with Cost의 경우 cost가 $-INF \times (\sum\limits l(a,b)-1)$보다 작은지 확인해주면 된다. ($\sum\limits l(a,b)$번 $INF$가 빼졌을 것이므로)
• Flow가 충분히 작은 경우에는 MCMF로도 충분히 빠른 시간 안에 돌아간다.

Code

• https://github.com/Pentagon03/Algorithms/blob/master/Flow/Circulation.cpp

Pro tips from Professional

• See: https://codeforces.com/blog/entry/105330?#comment-937339
  • It feels like the literature on network problems has 100 names for each thing.
• To say pedantically, "Circulation" and "Min Cost Circulation" is the only correct name to call them. If you think flows in a LP context, it is stupid to complicate things by introducing "source" and "sink". Why make two special cases that violate flow conservation? You can simply add an edge with infinite capacity from sink to source and compute a circulation.
• Then, if you want
  • If you want"Minimum cost maximum flow", set the sink -> source edge's cost as −∞ and compute Min cost circulation.
  • If you want "Minimum cost any flow", set the cost 0.
  • If you want "Minimum cost fixed flow", set the lower and upper bound cap to desired value(fixed flow)
• That's why they don't deserve different names.

Problem Reduction

Max Flow

• 모든 Cost를 0으로 세팅.
• $sink$에서 $src$로 $l(sink, src) = 0, \ u(sink, src) = \infty, \ c(sink, src) = -1$로 두면 $outflow(src)=inflow(src)$가 최대화되면서 max flow를 구해준다.

SSSP

• $l(sink, src)=u(sink,src)=1, c(sink, src) = -\infty$로 두고
• $l(u, v)=0, c(u,v) = \text{edge cost}$로 두면 Shortest Path를 구한다.

APSP

• Multi-Commodity Circulation으로 해결한다.
• 모든 Capacity를 무한으로 두고, 모든 $v(v-1)/2$ Commodity에 대해서 flow를 1씩 찾는다.

References

• https://koosaga.com/134
• https://blog.naver.com/kks227/221426339344
• https://jason9319.tistory.com/334
• https://sgc109.tistory.com/187