Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

Description

It is well known that many NP-hard problems are tractable in the class of bounded pathwidth graphs. In particular, path-decompositions of graphs are an important ingredient of dynamic programming algorithms for solving such problems. Therefore, computing the pathwidth and associated path-decomposition of graphs has both a theoretical and practical interest. In this paper, we design a Branch and Bound algorithm that computes the exact pathwidth of graphs and a corresponding path-decomposition. Our main contribution consists of several non-trivial techniques to reduce the size of the input graph (pre-processing) and to cut the exploration space during the search phase of the algorithm. We evaluate experimentally our algorithm by comparing it to existing algorithms of the literature. It appears from the simulations that our algorithm offers a significative gain with respect to previous work. In particular, it is able to compute the exact pathwidth of any graph with less than 60 nodes in a reasonable running-time (≤ 10 min.). Moreover, our algorithm also achieves good performance when used as a heuristic (i.e., when returning best result found within bounded time-limit). Our algorithm is not restricted to undirected graphs since it actually computes the vertex-separation of digraphs (which coincides with the pathwidth in case of undirected graphs).

Abstract (French)

Les décompositions en chemin de graphes sont très importants pour la conception d'algorithmes de programmation dynamique pour résoudre de nombreux problèmes NP-difficiles. Calculer la pathwidth et la décomposition en chemin correspondante sont donc d'un grand intérêt tant d'un point de vue théorique que pratique. Dans ce papier, nous proposons un algorithme de Branch and Bound qui calcule la pathwidth et une décomposition. Notre contribution principale réside dans les techniques que nous prouvons pour réduire la taille du graphe donné en entrée (pré- traitement) et réduire la taille de l'espace d'exploration de la phase de recherche de l'algorithme. Nous évaluons expérimentalement notre algorithme en le comparant aux algorithmes proposés dans la littérature. Les simulations montrent que notre algorithme apporte un gain significatif par rapport aux algorithmes existants. Il est capable de calculer la valeur exacte de la pathwidth de tout graphe composé d'au plus 60 sommets en un temps raisonnable (moins de 10 minutes). De plus, notre algorithme montre de bonnes performances lorsqu'il est utilisé en heuristique (c'est-à-dire lorsqu'il retourne le meilleur résultat trouvé en un temps donné). Notre algorithme n'est pas spécifique au graphes non orientés car il permet de calculer la vertex-separation des digraphes (qui coïncide avec la pathwidth dans le cas des graphes non orientés).

Additional details