最大反鎖や最小パス被覆を堅実に解く

概要

半順序集合の最大反鎖の計算は通常、Dilworth の定理を用いて最小パス被覆に帰着し、そこから更に二部マッチングへの帰着を行う。本記事では (最終的にかなり近いアルゴリズムにはなるものの) 直接最小カットに帰着する手法を説明する。また関連する話題として、最小パス被覆から二部マッチングへの帰着に対してフローを経由する解釈を与える。

互いに到達不能な頂点集合

問題

DAG $G = (V, E)$ が与えられる。 $S \subseteq V$ が良い集合であるとは、任意の $u, v \in S, \, u \neq v$ について $u$ から $v$ に到達不能であることを言う。最大化の良い集合 $S$ を求めよ。

これは、以下の問題と等価である。

問題

DAG $G = (V, E)$ が与えられる。 $V$ の各要素を上流 $U$ , 中流 $S$ , 下流 $D$ に分類する。ただし、中流から上流のように、流れを遡る辺が存在してはならない。また、中流同士をつなぐ辺も禁止とする。 $\lvert S \rvert$ を最大化せよ。

証明 (等価性)

流れを遡れないという条件から、中流は良い集合である。一方、良い集合 $S$ が与えられたとき、 $S$ に到達できる頂点 $\in V \setminus S$ を $U$ と定め、 $D := V \setminus \lbrace U \cup S \rbrace$ と定めると、これは適切な分割になっている。 $\blacksquare$

解法

言い換えによって得られた問題は頂点に $3$ 通りの値を割り当てる問題であり、コストを見ると Monge になっているため最小カットで解くことができる。 $k$ 値の最小カットについては最小カット問題の k 値への一般化 - noshi91のメモこの記事に記載した。

より一般的なフレームワーク (最小カット) に帰着しているため、二部マッチングへの帰着と比較して拡張性が高い。実際、cp-unspoiler において問われた頂点重み付きへの拡張は最小カットに帰着していれば容易である。一方で、二部マッチングは時間計算量に良い保証が付いているが、最小カットへの帰着ではそのような良い構造は無さそうだ。

最小パス被覆

最大反鎖問題を直接最小カットに帰着した場合最小パス被覆を考える必要はないため、本節は前節とは独立した内容である。

問題

DAG $G = (V, E)$ が与えられる。 $G$ におけるパスの集合 $\mathcal{P}$ であって、どの $v \in V$ も丁度 $1$ つの $P \in \mathcal{P}$ に含まれるものを考える。 $\lvert \mathcal{P} \rvert$ を最小化せよ。

解法

パスを考えるのだから、フローを用いた定式化が自然である。頂点に丁度 $1$ つのパスを通したいため、各 $v \in V$ を辺が入る側 $v _ {\mathrm{in} }$ と出る側 $v _ {\mathrm{out} }$ に分け、その間に流量下限と上限がどちらも $1$ であるような辺を張る。また、パスはどの頂点から始まってどの頂点で終わっても良いため、超頂点 $S, T$ を用意し、 $S$ から $v _ {\mathrm{in} }$ と $v _ {\mathrm{out} }$ から $T$ へ辺を張る。

以上の処理により、このグラフの流量制約を満たすフローであって、 $S$ から流出する量を最小化するものが求まればよい。流量下限付きフローの解き方の通り、まず $S \to v _ {\mathrm{in} } \to v _ {\mathrm{out} } \to T$ のフローを各 $v$ について流し、流量下限を達成しておく。あとは $T$ から $S$ にできるかぎり流し戻せばいい。実は、このときの残余グラフは二部マッチングへの帰着で得られるものと全く同じになっている。

二部マッチングへの直接の帰着はテクニカルだったが、フローを経由することで、特定の点から始まるパスにコストが掛かるなどの変種にも自然に対応できる。