@article{KorhonenBJ:JEA2018,
author = {Tuukka Korhonen and Jeremias Berg and Matti J\"arvisalo},
title = {Solving Graph Problems via Potential Maximal Cliques:
         An Experimental Evaluation of the Bouchitt\'e--Todinca Algorithm},
journal = {ACM Journal of Experimental Algorithmics},
volume = {24},
number = {1},
pages = {1.9},
year = {2019},
}

Abstract:

The BT algorithm of Bouchitt\'e and Todinca based on enumerating potential
maximal cliques, originally proposed for the treewidth and minimum fill-in
problems, yields improved exact exponential-time algorithms for various graph 
optimization problems related to optimal triangulations. While the BT
algorithm has received significant attention in terms of theoretical analysis,
less attention has been paid on engineering efficient implementations of the
algorithm for different problems and thereby on empirical studies on its
effectiveness in practice. In this work, we provide an experimental evaluation
of an implementation of the BT algorithm, based on our second place winning
entry in the 2nd Parameterized Algorithms and Computational Experiments
Challenge (PACE 2017), extended to several related graph problems: treewidth,
minimum fill-in, generalized and fractional hypertreewidth, and the total
table size problem. Instead of focusing on problem-specific optimization of BT
for a particular problem, our focus in this work is on studying the
applicability of BT more generally to a range of problems. Based on the
results, we conclude that an efficient implementation of the BT algorithm
yields an empirically competitive approach to each of the considered problems
when compared to available implementations of alternative problem-specific
algorithmic approaches.