Integer Linear Programming Formulation and Exact Algorithm for Computing Pathwidth

Computing the Pathwidth of a graph is the problem of finding a linear ordering of the vertices such that the width of its corresponding path decomposition is minimized. This problem has been proven to be NP-hard. Currently, some of the best exact methods for generic graphs can be found in the mathematical software project called SageMath. This project provides an integer linear programming model (IPSAGE) and an enumerative algorithm (EASAGE), which is exponential in time and space. The algorithm EASAGE uses an array whose size grows exponentially with respect to the size of the problem. The purpose of this array is to improve the performance of the algorithm. In this chapter we propose two exact methods for computing pathwidth. More precisely, we propose a new integer linear programming formulation (IPPW) and a new enumerative algorithm (BBPW). The formulation IPPW generates a smaller number of variables and constraints than IPSAGE. The algorithm BBPW overcomes the exponential space requirement by using a last-in-first-out stack. The experimental results showed that, in average, IPPW reduced the number of variables by 33.3 % and the number of constraints by 64.3 % with respect to IPSAGE. This reduction of variables and constraints allowed IPPW to save approximately 14.9 % of the computing time of IPSAGE. The results also revealed that BBPW achieved a remarkable use of memory with respect to EASAGE. In average, BBPW required 2073 times less amount of memory than EASAGE for solving the same set of instances.