Heuristic computation of exact treewidth

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 al...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-02
Main Author: Tamaki, Hisao
Format: Article
Language:English
Subjects:
Algorithms
Computation
Dynamic programming
Heuristic
Heuristic methods
Lower bounds
Solvers
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Tamaki's unpublished work on a heuristic use of the dynamic programming algorithm for deciding treewidth due to Bouchitt\'{e} and Todinca. The lower bound algorithm is based on the well-known fact that, for every minor \(H\) of \(G\), we have \(\tw(H) \leq \tw(G)\). Starting from a greedily computed minor \(H_0\) of \(G\), the algorithm tries to construct a sequence of minors \(H_0\), \(H_1\), \ldots \(H_k\) with \(\tw(H_i) < \tw(H_{i + 1})\) for \(0 \leq i < k\) and hopefully \(\tw(H_k) = \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.
ISSN:2331-8422