Skip to Main content Skip to Navigation
Conference papers

Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

David Coudert 1 Dorian Mazauric 2 Nicolas Nisse 1, 3
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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).
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Thursday, March 27, 2014 - 2:29:13 PM
Last modification on : Friday, January 7, 2022 - 9:34:03 AM
Long-term archiving on: : Friday, June 27, 2014 - 11:45:22 AM


Files produced by the author(s)


  • HAL Id : hal-00966851, version 1


David Coudert, Dorian Mazauric, Nicolas Nisse. Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth. 13th International Symposium on Experimental Algorithms, 2014, Copenhagen, Denmark. pp.46-58. ⟨hal-00966851⟩



Les métriques sont temporairement indisponibles