第２２回助教の会

本年度の最終回，第２２回助教の会では数理情報学第２研究室助教の小林佑輔さんに発表していただきました．発表タイトルは「制約付き２マッチング問題に対するアルゴリズム」ということで，最適化と離散構造に関するお話でした．

組合せ最適化の分野における代表的・古典的問題のひとつに「最大マッチング問題」があります．与えられたグラフにおいて頂点の重複がないように枝の本数を最大化する問題です．この問題の解ではひとつの頂点につながる枝は高々１本ですが，２本まで許すことにして枝数の最大化を考えるのが「最大2-マッチング問題」です．この問題の解はサイクルとパスの集まりになりますが，最大マッチング問題に帰着されることが知られているので計算は多項式時間でできます．さらに，「長さ$k$以下のサイクルは使わない」という制約を入れたものを「制約付き最大2-マッチング問題」と呼びます．禁止サイクル長$k$の値が変わることによって問題の難しさが大きく変わってくることが知られています．

最大マッチング問題では，各枝に重みを与えることにより重みの和の最大化を考えることもできます．制約付き最大2-マッチング問題で各枝に重みを与えたものを「制約付き最大2-マッチング問題（重み付き）」と呼ぶことにします．重み無しの場合と同様に，制約付き最大2-マッチング問題（重み付き）においても禁止サイクル長$k$を変えることで問題の難しさが変わることが知られています（図１）．

図１　先行研究

 
$k=3$である場合については，計算時間評価の境目に当たる問題になっており，一般に多項式時間で解けるかどうかは分かっていません．グラフの次数を3以下に限った場合にはHartvigsen-Li (2007)により問題が多項式時間で解かれることが示されていますが，提案されているアルゴリズムは単純ではありません．今回の小林さんの研究では，グラフの次数を3以下に限った場合を考え，問題の構造をうまく抽出して利用することにより単純な局所探索アルゴリズムを得ています（図２）．得られたアルゴリズムの正当性は，離散凸解析とグラフに関する考察から導かれます．

図２　研究成果

もう少し詳しく見てみます（図３）．まず，枝集合の次数列（枝集合が与えられ場合の各頂点の次数を並べたもの）に注目します．制約付き最大2-マッチング問題（重み付き）を直接解くのではなく，次数列ごとに枝の重みの和を最大化することを考えます．ここで重要なのは，

・次数列から対応する重みの最大和を求める関数は次数列に関してM凹関数である
・グラフの次数列が指定されれば重みの最大和は多項式時間で計算可能である

という２点です．後者により，局所探索が実行可能であることが分かります．次数列が与えられた場合の重みの最大和の計算可能性はグラフに関する考察から得られますが，その際にグラフの次数が3以下であることが効いてきます．さらに前者と離散凸解析の結果から，次数列に関する局所探索により制約付き最大2-マッチング問題（重み付き）が多項式時間で解けることが保証されます．

図３　提案アルゴリズム

今回の小林さんの発表は，「個別の問題における計算可能性・計算時間」というミクロな視点と「効率的な計算を可能にする離散構造」というマクロな視点とを組み合わせた研究についてでした．次数列を経由することで，考えていた問題の離散構造が分かりやすい形で現れ，局所探索という単純なアルゴリズムで問題が解けることが示されました．ミクロとマクロをつなぐ中間的な手段を経由することの「うまさ」，妙味が感じられる内容で，とても興味深いものでした．


数理５研助教 廣瀬善大

Jokyo20130218 from y-kobayashi