More Web Proxy on the site http://driver.im/

research-article

Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth

Authors:

Dorian Mazauric,

Nicolas NisseAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 21

Article No.: 1.3, Pages 1 - 23

https://doi.org/10.1145/2851494

Published: 29 January 2016 Publication History

Abstract

Path decompositions of graphs are an important ingredient of dynamic programming algorithms for solving efficiently many NP-hard problems. Therefore, computing the pathwidth and associated path decomposition of graphs has both a theoretical and practical interest. In this article, 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 nontrivial techniques to reduce the size of the input graph (preprocessing) 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 significant 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 (≤ 10min on a standard laptop). Moreover, our algorithm 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 directed pathwidth that generalizes the notion of pathwidth to digraphs.

References

[1]

Emgad H. Bachoore and Hans L. Bodlaender. 2005. New upper bound heuristics for treewidth. In Proceedings of the 4th International Workshop on Experimental and Efficient Algorithms (WEA), Lecture Notes in Computer Science, Vol. 3503, Sotiris E. Nikoletseas (Ed.), Springer, 216--227. http://dx.doi.org/10.1007/11427186_20.

Digital Library

[2]

Emgad H. Bachoore and H. L. Bodlaender. 2006. A branch and bound algorithm for exact, upper, and lower bounds on treewidth. In Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management (AAIM), Lecture Notes in Computer Science, Vol. 4041. Springer, 255--266.

Digital Library

[3]

János Barát. 2006. Directed path-width and monotonicity in digraph searching. Graphs Combin. 22, 2 (2006), 161--172.

Digital Library

[4]

Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, and Jan Obdrzálek. 2012. The dag-width of directed graphs. J. Comb. Theory, Ser. B 102, 4 (2012), 900--923.

Digital Library

[5]

Therese Biedl, Thomas Bläsius, Benjamin Niedermann, Martin Nöllenburg, Roman Prutkin, and Ignaz Rutter. 2013. Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings. In Graph Drawing, Lecture Notes in Computer Science, Vol. 8242. Springer, 460--471.

[6]

Daniel Bienstock. 1991. Graph searching, path-width, tree-width and related problems (a survey). DIMACS Ser. Discrete Math. Theor. Comput. Sci. 5 (1991), 33--49.

[7]

Daniel Bienstock and Paul D. Seymour. 1991. Monotonicity in graph searching. J. Algorithms 12, 2 (1991), 239--245.

Digital Library

[8]

Hans L. Bodlaender. 1996. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 6 (1996), 1305--1317.

Digital Library

[9]

Hans L. Bodlaender. 1998. A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1--2 (1998), 1--45.

Digital Library

[10]

Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. 2009. On problems without polynomial kernels. J. Comput. Syst. Sci. 75, 8 (2009), 423--434.

Digital Library

[11]

Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. 2013. An O(c^kn) 5-approximation algorithm for treewidth. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 499--508.

Digital Library

[12]

Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos. 2012a. A note on exact algorithms for vertex ordering problems on graphs. Theory Comput. Syst. 50, 3 (2012), 420--432.

Digital Library

[13]

Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos. 2012b. On exact algorithms for treewidth. ACM Trans. Algorithms 9, 1 (2012), 12.

Digital Library

[14]

Hans L. Bodlaender, Jens Gustedt, and Jan Arne Telle. 1998. Linear-time register allocation for a fixed number of registers. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM/SIAM, 574--583.

Digital Library

[15]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. 2012. Kernel bounds for structural parameterizations of pathwidth. In Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), Lecture Notes in Computer Science, Vol. 7357. Springer, 352--363.

Digital Library

[16]

Hans L. Bodlaender and Ton Kloks. 1996. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21, 2 (1996), 358--402.

Digital Library

[17]

Hans L. Bodlaender, Ton Kloks, and Dieter Kratsch. 1995. Treewidth and pathwidth of permutation graphs. SIAM J. Discrete Math. 8, 4 (1995), 606--616.

Digital Library

[18]

Hans L. Bodlaender and Arie M. C. A. Koster. 2007. On the maximum cardinality search lower bound for treewidth. Discrete Applied Mathematics 155, 11 (2007), 1348--1372.

Digital Library

[19]

Hans L. Bodlaender and Arie M. C. A. Koster. 2010. Treewidth computations I. Upper bounds. Inf. Comput. 208, 3 (2010), 259--275.

Digital Library

[20]

Hans L. Bodlaender and Arie M. C. A. Koster. 2011. Treewidth computations II. Lower bounds. Inf. Comput. 209, 7 (2011), 1103--1119.

Digital Library

[21]

Hans L. Bodlaender and Rolf H. Möhring. 1993. The pathwidth and treewidth of cographs. SIAM J. Discrete Math. 6, 2 (1993), 181--188.

Digital Library

[22]

N. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno, and N. Nisse. 2011. Tradeoffs in process strategy games with application in the WDM reconfiguration problem. Theor. Comput. Sci. 412, 35 (2011), 4675--4687.

Digital Library

[23]

D. Coudert, F. Huc, D. Mazauric, N. Nisse, and J.-S. Sereni. 2009. Reconfiguration of the routing in WDM networks with two classes of services. In Optical Network Design and Modeling (ONDM). IEEE, 1--6.

Digital Library

[24]

D. Coudert and J.-S. Sereni. 2011. Characterization of graphs and digraphs with small process number. Discr. Appl. Math. 159, 11 (2011), 1094--1109.

Digital Library

[25]

Bruno Courcelle and Mohamed Mosbah. 1993. Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci. 109, 1&2 (1993), 49--82.

Digital Library

[26]

N. Deo, S. Krishnamoorthy, and M. A. Langston. 1987. Exact and approximate solutions for the gate matrix layout problem. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 6 (1987), 79--84.

Digital Library

[27]

J. Díaz, J. Petit, and M. Serna. 2002. A survey on graph layout problems. ACM Comput. Surveys 34, 3 (2002), 313--356.

Digital Library

[28]

Andrew Drucker. 2012. New limits to classical and quantum instance compression. In 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 609--618.

Digital Library

[29]

A. Duarte, L. F. Escudero, R. Martí, N. Mladenovic, J. J. Pantrigo, and J. Sánchez-Oro. 2012. Variable neighborhood search for the vertex separation problem. Comput. OR 39, 12 (2012), 3247--3255.

Digital Library

[30]

Niklas Eén and Niklas Sörensson. 2004. An extensible SAT-solver. In Theory and Applications of Satisfiability Testing, Enrico Giunchiglia and Armando Tacchella (Eds.). Lecture Notes in Computer Science, Vol. 2919. Springer, Berlin, 502--518.

[31]

P. Erdös and A. Rényi. 1959. On random graphs. I. Public. Math. 6 (1959), 290--297.

[32]

Uriel Feige, Mohammad Taghi Hajiaghayi, and James R. Lee. 2005. Improved approximation algorithms for minimum-weight vertex separators. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC). ACM, 563--572.

Digital Library

[33]

Michael R. Fellows and Michael A. Langston. 1992. On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM J. Discrete Math. 5, 1 (1992), 117--126.

Digital Library

[34]

Vibhav Gogate and Rina Dechter. 2004. A complete anytime algorithm for treewidth. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (UAI’04). AUAI Press, 201--208. http://dl.acm.org/citation.cfm?id=1036843.1036868

Digital Library

[35]

Jens Gustedt. 1993. On the pathwidth of chordal graphs. Discr. Appl. Math. 45, 3 (1993), 233--248.

Digital Library

[36]

Alexander Hein and Arie M. C. A. Koster. 2011. An experimental evaluation of treewidth at most four reductions. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA), Lecture Notes in Computer Science, Vol. 6630. Springer, 218--229.

Digital Library

[37]

Paul Hunter and Stephan Kreutzer. 2008. Digraph measures: Kelly decompositions, games, and orderings. Theor. Comput. Sci. 399, 3 (2008), 206--219.

Digital Library

[38]

Thor Johnson, Neil Robertson, Paul D. Seymour, and Robin Thomas. 2001. Directed tree-width. J. Comb. Theory, Ser. B 82, 1 (2001), 138--154.

Digital Library

[39]

N. G. Kinnersley. 1992. The vertex separation number of a graph equals its pathwidth. Inform. Process. Lett. 42, 6 (1992), 345--350.

Digital Library

[40]

Lefteris M. Kirousis and Christos H. Papadimitriou. 1986. Searching and pebbling. Theor. Comput. Sci. 47, 3 (1986), 205--218.

[41]

Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, and Toshihiro Tano. 2012. Computing directed pathwidth in O(1.89ⁿ) time. In International Symposium on Parameterized and Exact Computation (IPEC), Lecture Notes in Computer Science, Vol. 7535. Springer, 182--193.

Digital Library

[42]

Ton Kloks, Hans L. Bodlaender, Haiko Müller, and Dieter Kratsch. 1993. Computing treewidth and minimum fill-in: All you need are the minimal separators. In 1st Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, Vol. 726. Springer, 260--271.

Digital Library

[43]

Yasuaki Kobayashi, Keita Komuro, and Hisao Tamaki. 2014. Search space reduction through commitments in pathwidth computation: An experimental study. In 13th International Symposium on Experimental Algorithms (SEA), Lecture Notes in Computer Science, Vol. 8504. Springer, 388--399.

Digital Library

[44]

Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, and Christos H. Papadimitriou. 1988. The complexity of searching a graph. J. ACM 35, 1 (1988), 18--44.

Digital Library

[45]

miplib 2010. MIPLIB - Mixed Integer Problem Library. (2010). http://miplib.zib.de/.

[46]

B. Monien and I. H. Sudborough. 1988. Min cut is NP-Complete for edge weighted trees. Theor. Comput. Sci. 58 (1988), 209--229.

Digital Library

[47]

Bruce A. Reed. 1992. Finding approximate separators and computing tree width quickly. In 24th Annual ACM Symposium on Theory of Computing (STOC). ACM, 221--228.

Digital Library

[48]

Neil Robertson and Paul D. Seymour. 1983. Graph minors. I. Excluding a forest. J. Comb. Theory, Ser. B 35, 1 (1983), 39--61.

[49]

Neil Robertson and Paul D. Seymour. 1986. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 3 (1986), 309--322.

[50]

Hein Röhrig. 1998. Tree Decomposition: A Feasibility Study. Diplomarbeit (master’s thesis), Universität des Saarlandes. Retrieved from http://hein.roehrig.name/dipl/.

[51]

rome. 2008. Rome graphs. Retrieved from http://www.graphdrawing.org/download/rome-graphml.tgz.

[52]

Jésus Sánchez-Oro, Juan José Pantrigo, and Abraham Duarte. 2014. Combining intensification and diversification strategies in VNS. An application to the vertex separation problem. Comput. Oper. Res. 52, Part B (2014), 209--219.

[53]

Paul D. Seymour and Robin Thomas. 1994. Call routing and the ratcatcher. Combinatorica 14, 2 (1994), 217--241.

[54]

K. Skodinis. 2003. Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time. J. Algorithms 47, 1 (2003), 40--59.

Digital Library

[55]

F. Solano. 2009. Analyzing two different objectives of the WDM network reconfiguration problem. In Proceedings of the IEEE Globecom. IEEE, 1--7.

Digital Library

[56]

F. Solano and M. Pióro. 2010. Lightpath reconfiguration in WDM networks. IEEE/OSA J. Opt. Commun. Netw. 2, 12 (2010), 1010--1021.

[57]

W. A. Stein and others. 2015. Sage Mathematical Software System (Version 6.6). The Sage Development Team.

[58]

Karol Suchan and Ioan Todinca. 2007. Pathwidth of circular-arc graphs. In Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science, Vol. 4769, Andreas Brandstädt, Dieter Kratsch, and Haiko Müller (Eds.). Springer, Berlin, 258--269.

Digital Library

[59]

Karol Suchan and Yngve Villanger. 2009. Computing pathwidth faster than 2ⁿ. In Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC), Lecture Notes in Computer Science, Vol. 5917. Springer, 324--335.

Digital Library

[60]

M. E. R. van Boxel. 2014. Improved Algorithms for the Computation of Special Junction Trees. Master’s thesis, Utrecht University. http://dspace.library.uu.nl/handle/1874/296605.

[61]

J.-W. van den Broek and H. Bodlaender. 2003. TreewidthLIB, A benchmark for algorithms for Treewidth and related graph problems. Retrieved from http://www.cs.uu.nl/research/projects/treewidthlib/.

[62]

vsplib 2012. VSPLIB. Retrieved from http://www.optsicom.es/vsp/.

[63]

Boting Yang and Yi Cao. 2008a. Digraph searching, directed vertex separation and directed pathwidth. Discrete Appl. Math. 156, 10 (2008), 1822--1837.

Digital Library

[64]

Boting Yang and Yi Cao. 2008b. Monotonicity in digraph search problems. Theor. Comput. Sci. 407, 1--3 (2008), 532--544.

Digital Library

Cited By

Bannach MBerndt S(2022)Recent Advances in Positive-Instance Driven Graph SearchingAlgorithms10.3390/a1502004215:2(42)Online publication date: 27-Jan-2022
https://doi.org/10.3390/a15020042
Coudert DNusser AViennot L(2022)Enumeration of Far-apart Pairs by Decreasing Distance for Faster Hyperbolicity ComputationACM Journal of Experimental Algorithmics10.1145/356916927(1-29)Online publication date: 13-Dec-2022
https://dl.acm.org/doi/10.1145/3569169
Duong HJaumard BCoudert DArmolavicius R(2021)Efficient Make-Before-Break Layer 2 ReoptimizationIEEE/ACM Transactions on Networking10.1109/TNET.2021.307858129:5(1910-1921)Online publication date: Oct-2021
https://doi.org/10.1109/TNET.2021.3078581
Show More Cited By

Index Terms

Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Grundy Distinguishes Treewidth from Pathwidth

Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the “price of generality” of these widths: as we transition from more ...
Exclusive graph searching vs. pathwidth

In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to ...
Circumference and Pathwidth of Highly Connected Graphs

Birmele [J Graph Theory 2003] proved that every graph with circumference t has treewidth at most t-1. Under the additional assumption of 2-connectivity, such graphs have bounded pathwidth, which is a qualitatively stronger conclusion. Birmele's theorem ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 21, Issue

Special Issue SEA 2014, Regular Papers and Special Issue ALENEX 2013

2016

404 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/2888418

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 January 2016

Accepted: 01 November 2015

Revised: 01 May 2015

Received: 01 October 2014

Published in JEA Volume 21

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

ANR project Stint
ANR program ≴Investments for the Future≵

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
314
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)3

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bannach MBerndt S(2022)Recent Advances in Positive-Instance Driven Graph SearchingAlgorithms10.3390/a1502004215:2(42)Online publication date: 27-Jan-2022
https://doi.org/10.3390/a15020042
Coudert DNusser AViennot L(2022)Enumeration of Far-apart Pairs by Decreasing Distance for Faster Hyperbolicity ComputationACM Journal of Experimental Algorithmics10.1145/356916927(1-29)Online publication date: 13-Dec-2022
https://dl.acm.org/doi/10.1145/3569169
Duong HJaumard BCoudert DArmolavicius R(2021)Efficient Make-Before-Break Layer 2 ReoptimizationIEEE/ACM Transactions on Networking10.1109/TNET.2021.307858129:5(1910-1921)Online publication date: Oct-2021
https://doi.org/10.1109/TNET.2021.3078581
Duong HJaumard BCoudert DArmolavicius R(2018)Efficient Make Before Break Capacity Defragmentation2018 IEEE 19th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR.2018.8850754(1-6)Online publication date: Jun-2018
https://doi.org/10.1109/HPSR.2018.8850754
Mallach S(2018)Linear ordering based MIP formulations for the vertex separation or pathwidth problemJournal of Discrete Algorithms10.1016/j.jda.2018.11.012Online publication date: Nov-2018
https://doi.org/10.1016/j.jda.2018.11.012
Mallach S(2018)Linear Ordering Based MIP Formulations for the Vertex Separation or Pathwidth ProblemCombinatorial Algorithms10.1007/978-3-319-78825-8_27(327-340)Online publication date: 17-Apr-2018
https://doi.org/10.1007/978-3-319-78825-8_27
Ding JZhou TLu ZYuan Y(2017)A quality and distance guided metaheuristic algorithm for vertex separation problemIEEE Access10.1109/ACCESS.2017.2740418(1-1)Online publication date: 2017
https://doi.org/10.1109/ACCESS.2017.2740418

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents