Integer programming models for the branchwidth problem

Abstract

We consider the problem of computing the branchwidth and an optimal branch decomposition of a graph. Branch decompositions and branchwidth were introduced in 1991 by Robertson and Seymour and were used in the proof of Graph Minors Theorem (GMT), a well known conjecture (Wagner's conjecture) in graph theory. The notions of branchwidth and branch decompositions have been proved to be useful for solving many NP-hard problems that have applications in fields such as graph theory, network design, sensor networks and biology. Branch decompositions have been utilized for problems such as the traveling salesman problem by Cook and Seymour, general minor containment and the branchwidth problem by Hicks by means of the relevant branch decomposition-based algorithms. Branch decomposition-based algorithms are fixed parameter tractable algorithms obtained by combining dynamic programming techniques with branch decompositions. The running time and space of these algorithms strongly depend on the width of the utilized branch decomposition. Thus, finding optimal or close to optimal branch decompositions is very important for the efficiency of the branch decomposition-based algorithms. Motivated by the vastness of the fields of application, we aim to increase the efficiency of the branch decomposition-based algorithms by investigating effective techniques to find optimal branch decompositions. We present three integer programming models for the branchwidth problem. Two similar formulations are based on the relationship of branchwidth problem with a special case of the Steiner tree packing problem. The third formulation is based on the notion of laminar separations. We utilize upper and lower bounds obtained by heuristic algorithms, reduction techniques and cutting planes to increase the efficiency of our models. We use all three models for the branchwidth problem on hypergraphs as well. We compare the performance of three models both on graphs and hypergraphs. Furthermore we use the third model for rank-width problem and also offer a heuristic for finding good rank decompositions. We provide computational results for this problem, which can be a basis of comparison for future formulations.