2019/09/17 by Tamaki, Hisao
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1909.07647
For a graph G, let Π(G) denote the set of all potential maximal cliques of G. For each subset Π of Π(G), let \tw(G, Π) denote the smallest k such that there is a tree-decomposition of G of width k whose bags all belong to Π. Bouchitté and Todinca observed in 2001 that \tw(G, Π(G)) is exactly the treewidth of G and developed a dynamic programming algorithm to compute it. Indeed, their algorithm can readily be applied to an arbitrary non-empty subset Π of Π(G) and computes \tw(G, Π), or reports that it is undefined, in time |Π||V(G)|O(1). This efficient tool for computing \tw(G, Π) allows us to conceive of an iterative improvement procedure for treewidth upper bounds which maintains, as the current solution, a set of potential maximal cliques rather than a tree-decomposition. We design and implement an algorithm along this approach. Experiments show that our algorithm vastly outperforms previously implemented heuristic algorithms for treewidth.