Push-Relabel メモ

Push-Relabel

最大流を求めるアルゴリズム

O(V^2 √E) (the highest label selection ruleを使用)

ざっくりと、容量を無視して流した後、流しすぎた分を削っていく感じ

 

手順

Dinic等と同様に残余辺も考え、各頂点に対し以下を定義する

流量f<最大流量cであるような辺e=(u,v)に対して、辺eの残余辺は最大流量c_f=c-fの辺(v,u)として定義される

excess(v):=vに入る流量-vから出る流量

label(v):=頂点vのラベル(各頂点の高さのようなイメージ、上から下に流れる)

 

source以外のlabelを0、label(source)を|V|として、sourceから出る辺全てに目一杯流した後(初期化)、以下の操作を繰り返す

 

・excessが正の頂点vを適当に選ぶ(このような頂点が存在しなければ終了)

・vから出る辺(v,to)であって、label(to)=label(v)-1を満たす辺を探す

→このような辺が存在する場合、この辺の容量が一杯になるか、excess(v)が尽きるまで目一杯流す(push)

→存在しない場合、xをvから出る辺(v,x)が存在するような頂点とし、label(v)=min(label(x))+1とする(relabel)

 

証明

s:=source,t:=sink

labelが以下の条件を満たすとき、そのlabel付けはvalidとする

・全ての残余辺(u,v)に対し、label(u)-1<=label(v)

・label(s)=|V|,label(t)=0

 

 

label付けがvalidである場合を考える

label(s)=|V|,label(t)=0に注意すると、

(u,t)パスが存在する場合、残余辺を一つ進むごとにlabelは高々1しか減少しないので、lavel(u)は残余グラフにおけるu-t間のunweighted distance(=辺の重みを考慮しない距離)の下界となる

(u,t)パスが存在しない場合、label(u)-|V|は残余グラフにおけるu-s間のunweighted distanceの下界となる

 

validなlabel付けが存在する場合、残余グラフにs-tパスは存在しない(存在を仮定すると、label(s)=|V|,label(t)=0よりs-t間のunweighted distanceの下界は|V|となってしまう)

 

 

初期化後、このアルゴリズムの実行中にlabel付けは常にvalidとなっていることを示す

初期化時のlabel付けはvalidであるから、push,relabel操作によってラベル付けがvalidなままであることを示せばよい

 

label(to)=label(v)-1を満たす辺(v,to)へのpushによって増えうる残余辺は(to,v)だけである、ここで残余辺(to,v)に対し、label(to)-1=label(v)-1<=label(v)となっているので、validなままである

 

relabelではlabel(v)の値が増加する

このとき、残余辺(v,to)があるとすると、元々validであることからlabel(v)-1<=label(to)であり、relabelを行う条件よりlabel(to)!=label(v)-1である

よってlabel(v)-1<min(label(to))である

new_label(v)=min(label(to))+1となるので、new_label(v)-1=min(label()to)<=label(to)が成り立つ(=validである)

 

残余辺(to,v)があるとすると、元々validであることからlabel(to)-1<=label(v)であり、label(v)が増加してもこの条件は成り立つ(=validである)

 

 

高速化テクニック

the highest label selection rule

O(V^2 √E)

実用的に高速(要検証)

excessが正の頂点を選ぶ時、labelが最大のものを選ぶ

 

Gap-relabeling

0<g<nを満たすあるgに対し、label(v)=gとなる頂点vが存在しない場合、g<label<nであるようなlabelを全てnにする

 

参考文献

https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm

https://tjkendev.github.io/procon-library/cpp/max_flow/push-relabel-highest.html

https://qiita.com/a-lilas/items/3bf338c7929f6951fa41

https://qiita.com/nariaki3551/items/65baee3c6ef0a6ffa136

https://github.com/ecnerwala/icpc-book/blob/master/kactl.pdf