TTPC 2015 N - 何かグラフの問題

• 問題
• AC

最短経路問題の双対と、この問題のような通称「牛ゲー」を負閉路検出で解くことの間にはギャップがあって、理解できていないままになっていたのだけど、ようやくわかった。

前提を確認する。重み付きグラフ $G := (V, E, (c_e)_{e \in E})$ とその頂点$s, t \in V$が与えられたとし、次の問題を$\operatorname{Dual}(s, t)$とする:

$\begin{aligned} \text{maximize} & \: & x_t - x_s &\\ \text{subject to} & \: & x_w - x_v \le c_e & \qquad \forall e := (v, w) \in E \end{aligned}$

$\operatorname{Dual}(s, t)$の双対問題を$\operatorname{Primal}(s, t)$とすると、$\operatorname{Primal}(s, t)$は点$s$から$t$への最短経路問題になる。具体的には、$E^-(v)$, $E^+(v)$をそれぞれ$v$に入る辺、$v$から出る辺とするとき、$\operatorname{Primal}(s, t)$は次のように書ける:

$\begin{aligned} \text{minimize} & \: &\sum_{e \in E} c_e y_e \\ \text{subject to} & & \sum_{e \in E^-(v)} y_e - \sum_{e \in E^+(v)} y_e & = 0 & \qquad \forall v \in V \setminus \{s, t\} \\ & & \sum_{e \in E^-(s)} y_e - \sum_{e \in E^+(s)} y_e & = -1 \\ & & \sum_{e \in E^-(t)} y_e - \sum_{e \in E^+(t)} y_e & =1 \\ & & y_e & \ge 0 & \qquad \forall e \in E \end{aligned}$

これはLP双対の定義に従って変形すれば確認できる。（ここは本題ではない。）

さて、『何かグラフの問題』やAsteroids2のような問題は$\operatorname{Dual}(s, t)$によく似ているが、まったく同じというわけではない。違いは、これらが目的関数を持たず、実行可能性を判定する問題だということだ。目的関数をどう選んでも実行可能性は変わらないのだから、好きに選べばよいと思うかもしれないが、双対問題が関わるとそうはいかない。

• 主問題が非有界 $\Rightarrow$ 双対問題が実行不可能
• 主問題が実行不可能 $\Rightarrow$ 双対問題は実行不可能または非有界

だから、最短経路問題$\operatorname{Primal}(s, t)$が非有界であることと$\operatorname{Dual}(s, t)$が実行不可能であることは一般に同値ではないのだ。では、何を解けばよいのか。

結論から言えば、実行可能性のみを判定したいときは、次の問題$\operatorname{Dual}_0$を解けばよい:

$\begin{aligned} \text{maximize} & \: & 0 &\\ \text{subject to} & \: & x_w - x_v \le c_e & \qquad \forall e := (v, w) \in E \end{aligned}$
最大化問題としては無意味だが、正しいLPである。このとき、$\operatorname{Dual}_0$の双対問題$\operatorname{Primal}_0$は

$\begin{aligned} \text{minimize} & \: &\sum_{e \in E} c_e y_e \\ \text{subject to} & & \sum_{e \in E^-(v)} y_e - \sum_{e \in E^+(v)} y_e = 0 & \qquad \forall v \in V \\ & & y_e \ge 0 & \qquad \forall e \in E \end{aligned}$

となる。$\operatorname{Primal}_0$を観察すると、これはグラフ$G$の最短閉路を探す問題であることがわかる。この際、閉路は1点につぶれていても良く、$y := 0$が常に実行可能解になっている。また、同じ辺を何回通ってもよい。したがって、グラフ$G$に負閉路があれば非有界($-\infty$)であり、なければ0が最適解になるが、重要なのは「常に実行可能」の部分である。このために次の3つがそれぞれ同値になる:

• グラフGが負閉路を持つ
• $\operatorname{Primal}_0$が非有界である
• $\operatorname{Dual}_0$が実行不可能である

したがって、$G$の負閉路検出で$\operatorname{Dual}_0$の実行可能性が判定できることになる。

参考:
http://www.me.titech.ac.jp/~mizu_lab/text/PDF-LP/LP2-dual.pdf
http://tokoharu.github.io/tokoharupage/docs/formularization.pdf