minimum path cover on DAG
推移律を満たす DAG において以下が成り立つ
最小パス被覆の連結成分数 \(=\) 最大独立集合の頂点数
また、最小パス被覆の連結成分数および最大独立集合の頂点数は二部グラフの最大マッチングで求まる
DAG の頂点数を \(N\) として、\(2N\) 個の頂点からなるグラフ \(G\) を考える
DAG のグラフで \(i\) から \(j\) に辺が張られているとき、\(G\) の頂点 \(i\) から頂点 \(i+N\) に辺を張る
このグラフにおける \(N - \text{最大マッチング数}\) が元の問題の答えになる