Heuristic computation of exact treewidth

• Item type: SIG Technical Reports(1)
• 公開日: 2023-01-12
• タイトル: Heuristic computation of exact treewidth
• タイトル / 言語: en
• タイトル: Heuristic computation of exact treewidth
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Meiji University
• 著者所属(英): en
• 著者所属(英): Meiji University
• 著者名: Hisao, Tamaki
• 著者名(英): Hisao, Tamaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We are interested in computing the treewidth tw(G) of a given graph G. Our approach is to design heuristic algorithms for computing a sequence of improving upper bounds and a sequence of improving lower bounds, which would hopefully converge to tw(G) from both sides. The upper bound algorithm extends and simplifies the present author's unpublished work on a heuristic use of the dynamic programming algorithm for deciding treewidth due to Bouchitte and Todinca. The lower bound algorithm is based on the well-known fact that, for every minor H of G, we have tw(H) ≦ tw(G). Starting from a greedily computed minor H0 of G, the algorithm tries to construct a sequence of minors H0, H1, . . .Hk with tw(Hi) < tw(Hi+1) for 0 ≦ i < k and hopefully tw(Hk) = tw(G). We have implemented a treewidth solver based on this approach and have evaluated it on the bonus instances from the exact treewidth track of PACE 2017 algorithm implementation challenge. The results show that our approach is extremely effective in tackling instances that are hard for conventional solvers. Our solver has an additional advantage over conventional ones in that it attaches a compact certificate to the lower bound it computes.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We are interested in computing the treewidth tw(G) of a given graph G. Our approach is to design heuristic algorithms for computing a sequence of improving upper bounds and a sequence of improving lower bounds, which would hopefully converge to tw(G) from both sides. The upper bound algorithm extends and simplifies the present author's unpublished work on a heuristic use of the dynamic programming algorithm for deciding treewidth due to Bouchitte and Todinca. The lower bound algorithm is based on the well-known fact that, for every minor H of G, we have tw(H) ≦ tw(G). Starting from a greedily computed minor H0 of G, the algorithm tries to construct a sequence of minors H0, H1, . . .Hk with tw(Hi) < tw(Hi+1) for 0 ≦ i < k and hopefully tw(Hk) = tw(G). We have implemented a treewidth solver based on this approach and have evaluated it on the bonus instances from the exact treewidth track of PACE 2017 algorithm implementation challenge. The results show that our approach is extremely effective in tackling instances that are hard for conventional solvers. Our solver has an additional advantage over conventional ones in that it attaches a compact certificate to the lower bound it computes.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2023-AL-191, 号 3, p. 1-6, 発行日 2023-01-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会