週刊 spaghetti_source

Tractability of Packing/Covering/Partitioning Problems

17:15

前回は全域木を複数個取る問題を題材に，マトロイド分割の説明をしました．マトロイドに関する話はこれで一段落にして，今回は複数全域木問題の周辺問題について，解ける・解けないを論じた[Bernath-Kiraly 2011]を紹介します．今回はコードなしで，軽めの話です．

＃前回の，コード紛失したものは見つかりました → https://topcoder-g-hatena-ne-jp.jag-icpc.org/spaghetti_source/20121124/1354351349 ．いつもどおり自信が無いのでプロの実装を待っています．

グラフ G = (V, E) の辺に関する判定問題を考えます．辺集合の性質 A, B について，次の３つのクラスの問題を考えます．

• 詰込問題（Packing） A ∩ B：詰込 X, Y であって（i.e., X ∩ Y = φ），X が A, Y が B を満たすものがあるか．
• 被覆問題（Covering） A ∪ B：被覆 X, Y であって（i.e., X ∪ Y = E），X が A, Y が B を満たすものがあるか．
• 分割問題（Partitioning） A + B：分割 X, Y であって（i.e., 詰込かつ分割），X が A, Y が B を満たすものがあるか．

たとえば，前回の全域木を k（=2）個取る問題は，全域木と全域木の詰め込みで，Spanning Tree ∩ Spanning Tree となります．重み（位数）の最適化と，存在判定にはギャップがありますが，少なくとも存在判定が解けない問題は最適化問題もNP-hardです．

結果

以下の７個の条件の組合せを考えます．

• P: パス
• Pst: s-t パス
• C: サイクル
• T: 木
• SpT: 全域木
• F: 森
• Cut: カット（i.e., 取り除くと非連結）

分割問題

Theorem. F+F, F+SpT, SpT+SpT, Cut+SpT, Cut+Cut 以外はNP-Complete

F/SpT系はマトロイド分割です．Cut+SpTは取れません（Cutを除くとSpTが存在しない）．Cut+Cutは，こう分割できることがbipartiteであることと同値であることから従います（可能側は自明．不可能側はbipartiteでないとき奇サイクルが存在することを使う）．

注目すべきは SpT+SpTがPで，T+T がNP-Completeになることでしょうか．SpTは極大Fとして特徴づけられるので，Tの難しさ（連結性）を正面から考えなくて済んでいる，ということだと思います．

被覆問題

被覆では，T, F, SpT は，重なっている部分を取り除くことで F との分割問題に帰着します．つまり P, Pst, C, Cut の４つの組合せが考慮対象になります．

Theorem. すべての組合せがNP-Complete

カバーは，難しい．

詰込問題

詰込では，P, T, F が絡むものは自明にすればよいので，そうでない Pst, C, SpT, Cut の４つの組合せが考慮対象になります．

Theorem. Pst∩SpT, C∩SpT 以外は P

Cut絡みは，基本的に自明です．Cut∩Cは小さくサイクルを取ってそれをカットの片側にするように頂点を分割します．Cut∩PstとCut∩Cutも同じノリです．SpT∩SpTはマトロイド分割です．Cut∩SpTが取れないのは分割と同じです．

Pst絡みですが，Pst+Ps't'は辺素パス問題のk=2の場合なので，グラフマイナータイプのアルゴリズムがあります [Robertson-Seymour 1995]．k=2の特殊ケースでは，グラフマイナー理論の確立よりも前に[Seymour 1980; Thomassen 1980; Shiloach 1980]でも論じられています．

Pst∩C, C∩Cは論文でアルゴリズムが提示されており，どちらも幅優先探索に基づきます．それほど実装は重くなさそうなので，気が向いたら実装するかもしれません．

参考文献

• [1] A. Bernath and Z. Kiraly (2011): "On the tractability of some natural packing, covering and partitioning problems", Technical Report.
• [2] N. Robertson and P. D. Seymour (1995): "Graph Minors XIII. The Disjoint Paths Problem", Journal of Combinatorial Theory, Series B, vol.63, no.1, pp.65-110.
• [3] P.D. Seymour (1980): "Disjoint paths in graphs", Discrete Mathematics, vol. 29, pp. 293-309.
• [4] Y. Shiloach (1980): "A polynomial solution to the undirected two paths problem", Journal on ACM, vol. 27, pp. 445-456.
• [5] C. Thomassen (1980): "2-linked graph", European Journal of Combinatorics, vol. 1, pp. 371-378.