DAGの最小道被覆問題 - 忘れても大丈夫

問題. DAGの最小道被覆問題

DAG $G = (V, A)$ が与えられる． $G$ の最小道被覆を求めよ．

定義. 有向非巡回グラフ
　有向非巡回グラフ(directed acyclic graph; DAG)とは有向閉路が存在しない有向グラフのことである．

定義. 道被覆
　有向グラフ $G$ の道被覆(path cover)とは， $G$ の有向道の集合でどの頂点もちょうど1つの有向道に含まれるもののことである．ここで，有向道とは頂点の重複がないものとし，有向道を道と呼ぶことにする．
　サイズが最小の道被覆を最小道被覆(minimum path cover)という．

例. 最小道被覆

有向グラフ $G = (\{1, 2, 3, 4, 5, 6, 7, 8\}, \{12,13,34,38,45,62,67,73,85\})$ としたとき， $G$ の道被覆は $C = \{12345, 67, 8\}$ となります．また，頂点1だけからなるものも道とします．したがって，どんなグラフでも道被覆は存在します．
$C$ は3つの道を含むのでサイズ3となり，後で確認しますが $C$ は $G$ の最小道被覆となります．
f:id:tatanaideyo:20180602082006p:plain:w300

解法. 二部グラフの最大マッチング問題への帰着

一般グラフの最小道被覆問題はNP困難ですが，DAGに制限すると多項式時間で解くことができます．解法を大雑把に言うと二部グラフの最大マッチング問題に帰着します．ここでの解法と証明は蟻本のpp. 242--244 を参考にしています．

DAG-MSCP
入力 : DAG $G = (V, A)$
出力 : $G$ の最小道被覆のサイズ
Step1. 部グラフを $X, Y$ とする二部グラフ $H = (X \cup Y, E)$ を次のように構成する．
　　　　・ $X = Y = V$
　　　　・ $E = \{\{u, v\} \mid u \in X, v \in Y, uv \in A\}$
Step2. $H$ の最大マッチング $M \subseteq E$ を求める
Step3. $|V| - |M|$ を出力する

上の例で用いたグラフに対して上のアルゴリズムを適用したときに得られる二部グラフとその最大マッチングは次のようになります．このとき，最大マッチングは $\{12',23',34',45',67'\}$ となり，道被覆に含まれる弧全体と等しくなります．
f:id:tatanaideyo:20180602082006p:plain:w300 f:id:tatanaideyo:20180602091330p:plain:w200

命題. DAG-MSCP の解の正当性
証明.
$G$ の任意の道 $P$ を考える． $P$ の頂点集合と弧集合をそれぞれ $V(P), A(P)$ とすると， $|V(P)| = |A(P)| + 1$ となる．したがって， $G$ の任意の道被覆 $C = \{P_1, P_2, ..., P_k\}$ に対して， $V(P_i) \cap V(P_j) = \emptyset, A(P_i) \cap A(P_j) = \emptyset$ 　 $(i \neq j \in \{1, ..., k\})$ より，
　 $\left|\bigcup_{i=1}^{k} V(P) \right| = \left|C \right| + \left|\bigcup_{i=1}^{k} A(P) \right|$
となる．ここで， $C$ は $G$ のすべての頂点を含み， $C$ の道は互いに素であることから，
　 $|C| = |V| - \sum_{i=1}^{k} \left|A(P_i) \right|$
となる．よって，道被覆のサイズの最小化は道被覆に含まれる弧の最大化に等しい．
ここで， $\sum_{i=1}^{k} \left|A(P_i) \right|$ を最大にする $G$ の道被覆 $C$ を求めることを考える．DAG-MSCP のステップ1 で構成した二部グラフを $H = (X \cup Y, E)$ とする．
$H$ のマッチング $M \subseteq E$ を考える． $\{u, v\} \in M \,(u \in X, v \in Y)$ を $G$ の弧 $uv \in A$ を道被覆のある道の弧として選択することにして， $M$ に対応する $G$ の弧全体を $A_M$ とする． $X$ と $Y$ の各頂点が $M$ によって被覆される辺は高々1つなので， $G$ の各頂点の $A_M$ による出次数と入次数は高々1である．よって， $A_M$ は $G$ の道被覆となる．
逆に， $G$ の道被覆によって選ばれる弧全体は $H$ のマッチングとなる．したがって， $G$ の道被覆に含まれる弧の最大化は $H$ のマッチングのサイズの最大化に等しい．　❏