Development of treewidth algorithms based on path-like tree-decompositions

点击翻译按钮获取中文摘要

昨年度は、グラフ縮約に基づいた木幅下界を順次改良する方法において大きな進展があった。この下界アルゴリズムと上界アルゴリズムを組み合わせることにより、従来法では解くことのできなかった規模のグラフに対して厳密な木幅を計算することが可能になった、今年度は、グラフ縮約に基づいた再帰により木幅を計算する方法を発見することができた。この方法では下界の計算と上界の計算が一体化されている。その考え方を示す。グラフGの木幅をtw(G)で表す。また、Gをその辺eによって縮約してできるグラフをG/eで表す。与えれらたグラフGが従来法で容易に解ける規模であれば、従来法で解く。そうでない場合、Gの辺eを選び、k = tw(G/e)を再帰的に計算する。kはtw(G)の下界隈であり、k+1はtw(G)の上界である。実際、G/eの幅kの木分解をGの木分解に自然に「翻訳」することにより、Gの幅k+1以下の木分解を容易に得ることができる。この翻訳法を工夫することにより、得られた木分解の幅がkである可能性を増すことができるというのが重要な発見である。ひとつの辺に対しての再帰結果からtw(G)を決定できない場合は、複数の辺に対して再帰を行うことにより、成功の可能性をさらに増加させることができる。この方法の詳細を設計し、従来法および昨年度開発した上記のアルゴリズムをはるかに凌駕する性能の木幅アルゴリズムを得ることができた。この方法自体は、研究計画の時点の「パス的木分解に基づく」という構想からは大きく逸脱しているが、実用的に優れた性能の木幅アルゴリズムを開発するという目的は、期待以上に満足するものである。また、この再帰的アルゴリズムの一部で用いている上界改良アルゴリズムはパス的木分解のアイディアを一部使用しており、構想はそういう形で結果に寄与している。