Maximum flow - Push-relabel Algorithm

Maximum flow - Push-relabel algorithm - Algorithms for Competitive Programming

 

(신기하게도 Push-relabel algorithm (Preflow-push algorithm)을 만든 두 사람 중 한 명인 Robert Tarjan은 우리가 아는 그 Targan's strongly connected components algorithm뿐만 아니라 이름만 들어본 Fibonacci heap과 splay tree를 만들었다고 한다. 정말 대단하다..)

 

 

Edmond-Karp algorithm과 같이 flow network가 주어졌을 때 source에서 sink로의 maximum flow를 구하는 알고리즘이다. Edmond-Karp algorithm의 시간복잡도는 O(\( VE^2 \))인 반면 Push-relabel algorithm의 시간복잡도는 O(\(V^2E\)) 이다 (\(E\)를 \(V^2\)라고 가정한다면 O(\(V^4\))).

 

 

먼저 preflow를 정의하자. Push-relabel algorithm에서의 flow function f와 capacity function c는 다음과 같은 조건을 만족한다.

 

$$ 0 \leq f(e) \leq c(e) $$

and

$$ \sum_{(v, u) \in E} f((v, u)) \geq \sum_{(u, v) \in E} f((u, v)) $$

 

첫 번째 조건은 자명하다 (간선의 capacity보다 더 많은 물이 흐를 수는 없으니). 하지만 두 번째 식은 조금 이상해 보인다. Edmond-Karp에서 두 번째 식은 등식이다 (source와 sink를 제외한 모든 정점에 대해, 들어오는 flow와 나오는 flow가 같은 것은 당연하다). 반면 Push-relabel algorithm에서는 들어오는 flow보다 나가는 flow가 적은 preflow를 고려하여 부등식이 나온다. 그리고 이 preflow에 대해 excess function x를 다음과 같이 정의한다.

 

$$ x(u) = \sum_{(v, u) \in E} f((v, u)) - \sum_{(u, v) \in E} f((u, v)) $$

 

정점 \(u\)에 들어온 물보다 나가는 물이 적으므로 \(u\)에 \(x(u)\)만큼 물이 고여있다고 생각하면 된다.

 

따라서 source와 sink를 제외한 모든 정점에 대해 이 excess를 0으로 만들어주게 되면 Edmond-Karp와 같은 조건을 만족하는 preflow가 사라진 valid flow를 구할 수 있다. 그리고 그 flow는 maximum flow이다.

 

조금 더 디테일하게 들어가자면 excess가 있는 모든 정점에 대해 그만큼의 물을 이웃한 정점들로 보내는 과정을 반복하여 정점에서 물을 빼내 excess를 0으로 만들면 된다.

 

 

이때 두 가지의 문제점이 있다. 첫 번째 문제는 이 과정이 과연 끝나는 것을 보장할 수 있는가이다. 두 번째 문제는 이런 과정으로 구한 flow가 maximum flow임을 단언할 수 있는가이다.

 

이를 증명하기 위해 labeling function (height function이라고도 하는) h가 필요하다. 만약 \( h(s) = |V| \), \( h(t) = 0 \)이고 residual graph에서 capacity가 양수인 모든 간선 (\(u\), \(v\))에 대해 (\(u\)에서 \(v\)로 물이 흐를 수 있을 때) \( h(u) \leq h(v) + 1 \)를 만족한다면 labeling이 valid 하다고 정의한다.

(높은 곳에서 낮은 곳으로 물이 흐르는 것을 생각하는 것이 편하다. 제일 높은 곳은 source이고 제일 낮은 곳은 sink이다. 다른 정점들은 그사이를 담당한다.)

 

valid 하게 labeling 된 residual graph에서 s에서 t로 가는 augmenting path는 없다. augmenting path가 있다고 가정했을 때 path에 속한 간선의 최대 개수는 \( |V| - 1 \)이다. 간선은 height를 최대 1만큼 줄일 수 있는데 sink의 height가 \( |V| \)이고 sink의 height가 0인 것을 생각하였을 때 그러한 path는 존재하지 않는다. 따라서 과정이 종료하기만 하면 augmenting path가 존재하지 않으므로 maximum flow를 구한 것이라 볼 수 있다.

(valid flow, valid labeling을 만족하면 maximum flow를 구할 수 있음)

(여기서 valid flow란 source와 sink를 제외한 나머지 모든 정점에 대해 들어가고 나오는 flow가 같을 때를 의미한다.)

 

Fold-Fulkerson이 valid flow를 만족하며 augmenting path가 존재하지 않을 때까지, 즉 valid labeling이 가능할 때까지 과정을 진행한다고 한다면 반대로 Push-relabel은 valid labeling을 만족하며 (augmenting path가 없는 조건을 유지한 채로) valid flow를 만족할 때까지 과정을 진행한다.

 

 

알고리즘은 다음과 같다.

 

valid labeling을 만족하기 위해 처음에는 source와 연결된 간선에 capacity만큼 flow를 흘려준다 (\( f((s, u)) = c((s, u)) \)). 그러면 \( h(s) = |V| \) 이고 다른 정점들의 height를 0으로 하는 valid labeling을 할 수 있다.

 

그런 다음 상황에 맞게 PUSH와 RELABEL을 반복해주면 된다.

 

PUSH는 excess가 양수인 정점 \( u \)에 대해 \( h(u) = h(v) + 1 \)을 만족하는 \( v \)에게 \( \min(x(u), c((u, v)) - f((u, v))) \)만큼의 물을 push 할 수 있다.

 

만약 excess가 양수인 정점이 인접한 정점들에게 PUSH를 할 수 없다면 valid labeling을 만족하는 한에서 최대한 해당 정점의 높이를 올린다. 이를 RELABEL이라 한다.

 

요약하자면 처음에 valid preflow와 valid labeling을 만족하도록 설정을 해주고 PUSH와 RELABEL을 더 이상 할 수 없을 때가지 반복해준다. 그렇게 preflow를 없애서 maximum flow를 얻을 수 있다.

 

 

const int inf = 1000000000;

int n;
vector<vector<int>> capacity, flow;
vector<int> height, excess, seen;
queue<int> excess_vertices;

void push(int u, int v)
{
    int d = min(excess[u], capacity[u][v] - flow[u][v]);
    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
    if (d && excess[v] == d)
        excess_vertices.push(v);
}

void relabel(int u)
{
    int d = inf;
    for (int i = 0; i < n; i++) {
        if (capacity[u][i] - flow[u][i] > 0)
            d = min(d, height[i]);
    }
    if (d < inf)
        height[u] = d + 1;
}

void discharge(int u)
{
    while (excess[u] > 0) {
        if (seen[u] < n) {
            int v = seen[u];
            if (capacity[u][v] - flow[u][v] > 0 && height[u] > height[v])
                push(u, v);
            else 
                seen[u]++;
        } else {
            relabel(u);
            seen[u] = 0;
        }
    }
}

int max_flow(int s, int t)
{
    height.assign(n, 0);
    height[s] = n;
    flow.assign(n, vector<int>(n, 0));
    excess.assign(n, 0);
    excess[s] = inf;
    for (int i = 0; i < n; i++) {
        if (i != s)
            push(s, i);
    }
    seen.assign(n, 0);

    while (!excess_vertices.empty()) {
        int u = excess_vertices.front();
        excess_vertices.pop();
        if (u != s && u != t)
            discharge(u);
    }

    int max_flow = 0;
    for (int i = 0; i < n; i++)
        max_flow += flow[i][t];
    return max_flow;
}

 

 

위의 코드에서는 excess가 양수인 정점들을 모두 queue에 넣어 관리한다. 하지만 현재 시점에서 양수 excess를 가진 정점 중 가장 높은 정점들만을 모아 PUSH와 RELABLE을 해서 시간 복잡도를 \( O(VE + V^2\sqrt{E}) \) 만큼으로 만들 수 있다. 최악의 경우 \( O(V^3) \) 이다.

 

const int inf = 1000000000;

int n;
vector<vector<int>> capacity, flow;
vector<int> height, excess;

void push(int u, int v)
{
    int d = min(excess[u], capacity[u][v] - flow[u][v]);
    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
}

void relabel(int u)
{
    int d = inf;
    for (int i = 0; i < n; i++) {
        if (capacity[u][i] - flow[u][i] > 0)
            d = min(d, height[i]);
    }
    if (d < inf)
        height[u] = d + 1;
}

vector<int> find_max_height_vertices(int s, int t) {
    vector<int> max_height;
    for (int i = 0; i < n; i++) {
        if (i != s && i != t && excess[i] > 0) {
            if (!max_height.empty() && height[i] > height[max_height[0]])
                max_height.clear();
            if (max_height.empty() || height[i] == height[max_height[0]])
                max_height.push_back(i);
        }
    }
    return max_height;
}

int max_flow(int s, int t)
{
    height.assign(n, 0);
    height[s] = n;
    flow.assign(n, vector<int>(n, 0));
    excess.assign(n, 0);
    excess[s] = inf;
    for (int i = 0; i < n; i++) {
        if (i != s)
            push(s, i);
    }

    vector<int> current;
    while (!(current = find_max_height_vertices(s, t)).empty()) {
        for (int i : current) {
            bool pushed = false;
            for (int j = 0; j < n && excess[i]; j++) {
                if (capacity[i][j] - flow[i][j] > 0 && height[i] == height[j] + 1) {
                    push(i, j);
                    pushed = true;
                }
            }
            if (!pushed) {
                relabel(i);
                break;
            }
        }
    }

    int max_flow = 0;
    for (int i = 0; i < n; i++)
        max_flow += flow[i][t];
    return max_flow;
}

 

 

더 자세한 설명은 구사과님의 포스트를 참조하세요.

Push Relabel Algorithm (1)