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

基于类路径树分解的树宽算法的开发

基本信息

批准号：
21K11761
负责人：
玉木久夫
金额：
$ 2.66万
依托单位：
Meiji University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

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

去年，如何根据降低图逐渐改善树的底线取得了很大进展。通过将此下限算法与上限算法相结合，可以计算出无法通过常规方法求解的尺度图的确切树宽度。今年，我们能够发现一种基于绘制的递归来计算树宽的方法。该方法集成了上限的下限和计算的计算。展示这个想法。图G的树宽度表示为TW（G）。另外，可以通过e缩合E将其转换为G的图表示为g/e。如果给定的图G是可以使用常规方法轻松求解的比例，则将解决常规方法。否则，请选择G的边缘E并递归计算K = TW（g/e）。 K是TW（G）的下边界，K+1是TW（G）的上边界。实际上，通过自然地将g/e的树的树分解为g的宽度k k/e，很容易获得g+1宽度或更小的g的树分解。一个重要的发现是，通过发明这种翻译方法，可以增加所获得的树分解宽度为k的可能性。如果无法从一个边的递归结果中确定TW（g），则多个边缘的递归可以进一步增加成功的机会。该方法的详细信息旨在获得具有性能的树宽算法，该算法远远超过了传统方法，并且去年开发的上述算法。尽管该方法本身远离了研究计划时“基于基于路径的树的分解”的概念，但开发实际上较高的性能树宽度算法的目的比预期的要令人满意。此外，在某些递归算法中使用的上限改进算法使用路径处理的一部分，并且该概念以这种方式有助于结果。