Computational study on Bidimensionality Theory based algorithms

Bidimensionality theory provides a general framework for developing subexponential fixed parameter algorithms for NP-hard problems. A representative example of such algorithms is the one for the longest path problem in planar graphs. The largest grid minor and the branch-decomposition of a graph play an important role in bidimensionality theory. The best known approximation algorithm for computing the largest grid minor of a planar graph has the approximation ratio 3. In this thesis, we report a computational study on a branch-decomposition based algorithm for the longest path problem in planar graphs. We implement the 3-approximation algorithm for computing large grid minors. We also design and implement an exact algorithm for computing the largest cylinder minor in planar graphs to evaluate the practical performance of the 3-approximation algorithm. The results show that the bidimensional framework is practical for the longest path problem in planar graphs.