容量下限などが付いている最小費用流

概要

辺の流量に下限があったりする最小費用流を、思いつく範囲で一般化してみました。

記法の定義

$G = (V, E)$ を有向グラフとします。フロー $\xi \in \mathbb{Z} ^ E$ に対して、その境界 $\partial \xi \in \mathbb{Z} ^ V$ を $\displaystyle \partial \xi _ v = \sum _ {(v, u) \in E} \xi _ u - \sum _ {(u, v) \in E} \xi _ u$ で定義します。つまり、境界は各頂点から流れ出る量を表しています。

ベクトルに対して不等号を使ったときは、全ての成分について同時にその不等号が成り立つものと解釈します。例: $0 \leq c \Leftrightarrow c$ は非負ベクトル

$\lVert \cdot \rVert _ 1$ は $L ^ 1$ ノルムで、成分毎の絶対値の和です。

基本的な最小費用流

枝コスト $\gamma \in \mathbb{Z} _ {\geq 0} ^ {E}$
容量上限 $\overline{c} \in \mathbb{Z} ^ {E}$
source $s \in V$
sink $t \in V$
流量 $f \in \mathbb{Z} _ {\geq 0}$
$s \neq t$

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi \cr \text{subject to}&\quad 0 \leq \xi \leq \overline{c} \cr &\quad \partial \xi _ v = \begin{cases} f &\quad (v = s) \cr -f &\quad (v = t) \cr 0 &\quad (\text{otherwise}) \end{cases} \end{align}

$0 \leq \overline{c}$ の場合 ACL を使うとそのまま解くことができます。 $0 \leq \overline{c}$ でない場合は解がありません。時間計算量は $\mathrm{O}(f (\lvert V \rvert + \lvert E \rvert) \log (\lvert V \rvert + \lvert E \rvert))$ です。

b-flow

枝コスト $\gamma \in \mathbb{Z} _ {\geq 0} ^ {E}$
容量上限 $\overline{c} \in \mathbb{Z} ^ {E}$
供給 $x \in \mathbb{Z} ^ {V}$

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi \cr \text{subject to}&\quad 0 \leq \xi \leq \overline{c} \cr &\quad \partial \xi = x \end{align}

$\displaystyle \sum _ {x _ v \gt 0} x _ v = - \sum _ {x _ v \lt 0} x _ v$ が成り立っていないときは解がありません。そうでないとき

超頂点 $s, t$ を作成する
$x _ v \gt 0$ である $v$ に対して、 $s$ から $v$ に容量上限 $x _ v$ コスト $0$ の辺を張る
$x _ v \lt 0$ である $v$ に対して、 $v$ から $t$ に容量上限 $- x _ v$ コスト $0$ の辺を張る
$s$ から $t$ に $\lVert x \rVert _ 1 / 2$ 流す

で前述の問題に帰着されます。時間計算量は $\mathrm{O}(\lVert x \rVert _ 1 (\lvert V \rvert + \lvert E \rvert) \log (\lvert V \rvert + \lvert E \rvert) )$ です。

容量下限付き

枝コスト $\gamma \in \mathbb{Z} _ {\geq 0} ^ {E}$
容量下限 $\underline{c} \in \mathbb{Z} ^ {E}$
容量上限 $\overline{c} \in \mathbb{Z} ^ {E}$
供給 $x \in \mathbb{Z} ^ {V}$

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi \cr \text{subject to}&\quad \underline{c} \leq \xi \leq \overline{c} \cr &\quad \partial \xi = x \end{align}

これは

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} (\xi - \underline{c}) + \gamma ^ {\top} \underline{c} \cr \text{subject to}&\quad 0 \leq \xi - \underline{c} \leq \overline{c} - \underline{c} \cr &\quad \partial (\xi - \underline{c}) = x - \partial \underline{c} \end{align}

と書き換えることができます。したがって $\xi - \underline{c}$ をフローと思うことで前述の問題に帰着されます。時間計算量は $\mathrm{O}(\lVert x - \partial \underline{c} \rVert _ 1 (\lvert V \rvert + \lvert E \rvert) \log (\lvert V \rvert + \lvert E \rvert)) \subseteq \mathrm{O}( (\lVert x \rVert _ 1 + \lVert \underline{c} \rVert _ 1) (\lvert V \rvert + \lvert E \rvert) \log (\lvert V \rvert + \lvert E \rvert) )$ です。

枝コストが負

枝コスト $\gamma \in \mathbb{Z} ^ {E}$
容量下限 $\underline{c} \in \mathbb{Z} ^ {E}$
容量上限 $\overline{c} \in \mathbb{Z} ^ {E}$
供給 $x \in \mathbb{Z} ^ {V}$

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi \cr \text{subject to}&\quad \underline{c} \leq \xi \leq \overline{c} \cr &\quad \partial \xi = x \end{align}

$\gamma _ a \lt 0$ である全ての $a \in E$ について、

$a$ の向きを逆にする
$\gamma _ a \leftarrow - \gamma _ a$
$(\underline{c} _ a, \overline{c} _ a) \leftarrow (-\overline{c} _ a, -\underline{c} _ a)$

とすると、前述の問題に帰着されます。時間計算量はコストが負の辺の容量上限で変わるので、適宜計算してください。

供給が区間、境界に線形のコスト

枝コスト $\gamma \in \mathbb{Z} ^ {E}$
容量下限 $\underline{c} \in \mathbb{Z} ^ {E}$
容量上限 $\overline{c} \in \mathbb{Z} ^ {E}$
境界コスト $\zeta \in \mathbb{Z} ^ V$
供給下限 $\underline{x} \in \mathbb{Z} ^ {V}$
供給上限 $\overline{x} \in \mathbb{Z} ^ {V}$

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi + \zeta ^ {\top} \partial \xi \cr \text{subject to}&\quad \underline{c} \leq \xi \leq \overline{c} \cr &\quad \underline{x} \leq \partial \xi \leq \overline{x} \end{align}

超頂点 $s$ を作成する
各 $v \in V$ について、 $s$ から $v$ に容量下限 $\underline{x} _ v$ 容量上限 $\overline{x} _ v$ コスト $\zeta _ v$ の辺を張る
供給 $x = 0$ として前述の問題に帰着

その他

$\mathbb{Z}$ の場合で議論しましたが、コストが $\mathbb{R}$ の場合や、 $\pm \infty$ が含まれる場合も概ね同様に議論できます。ただし容量下限付きを下限 $0$ に帰着するときに下限 $\underline{c}$ に $- \infty$ が含まれていると壊れます。これは容量上限 $+ \infty$ でコストが負の辺に対して「あらかじめ限界まで流しておく」が使えないことと同じです。