Document Open Access Logo

Cutwidth: Obstructions and Algorithmic Aspects

Authors Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2016.15.pdf
  • Filesize: 0.56 MB
  • 13 pages

Document Identifiers

Author Details

Archontia C. Giannopoulou
Michal Pilipczuk
Jean-Florent Raymond
Dimitrios M. Thilikos
Marcin Wrochna

Cite As Get BibTex

Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Cutwidth: Obstructions and Algorithmic Aspects. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.IPEC.2016.15

Abstract

Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k. We prove that every minimal immersion obstruction for cutwidth at most k has size at most 2^O(k^3*log(k)).

As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time 2^O(k^2*log(k))*n, where k is the optimum width and n is the number of vertices. While being slower by a log k-factor in the exponent than the fastest known algorithm, due to Thilikos, Bodlaender, and Serna [J. Algorithms 2005], our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts.

Subject Classification

Keywords
  • cutwidth
  • obstructions
  • immersions
  • fixed-parameter tractability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Patrick Bellenbaum and Reinhard Diestel. Two short proofs concerning tree-decompositions. Combinatorics, Probability & Computing, 11(6):541-547, 2002. Google Scholar
  2. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. Google Scholar
  3. Hans L. Bodlaender and Ton Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358-402, 1996. Google Scholar
  4. Heather Booth, Rajeev Govindan, Michael A. Langston, and Siddharthan Ramachandramurthi. Cutwidth approximation in linear time. In Proceedings of the Second Great Lakes Symposium on VLSI, pages 70-73. IEEE, 1992. Google Scholar
  5. Josep Díaz, Jordi Petit, and Maria J. Serna. A survey of graph layout problems. ACM Comput. Surv., 34(3):313-356, 2002. Google Scholar
  6. Martin Fürer. Faster computation of path-width. In Veli Mäkinen, J. Simon Puglisi, and Leena Salmela, editors, Combinatorial Algorithms: 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings, pages 385-396, Cham, 2016. Springer International Publishing. Google Scholar
  7. Michael R. Garey and David S. Johnson. Computers and intractability, volume 174. Freeman New York, 1979. Google Scholar
  8. James F. Geelen, A. M. H. Gerards, and Geoff Whittle. Branch-width and well-quasi-ordering in matroids and graphs. J. Comb. Theory, Ser. B, 84(2):270-290, 2002. A correction is available at URL: http://www.math.uwaterloo.ca/~jfgeelen/Publications/bn-corr.pdf.
  9. Rajeev Govindan and Siddharthan Ramachandramurthi. A weak immersion relation on graphs and its applications. Discrete Mathematics, 230(1):189-206, 2001. Google Scholar
  10. Pinar Heggernes, Daniel Lokshtanov, Rodica Mihai, and Charis Papadopoulos. Cutwidth of split graphs and threshold graphs. SIAM J. Discrete Math., 25(3):1418-1437, 2011. Google Scholar
  11. Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, and Jesper Nederlof. Computing the cutwidth of bipartite permutation graphs in linear time. SIAM J. Discrete Math., 26(3):1008-1021, 2012. Google Scholar
  12. Mamadou Moustapha Kanté and O-joung Kwon. An upper bound on the size of obstructions for bounded linear rank-width. CoRR, arXiv:1412.6201, 2014. Google Scholar
  13. Jens Lagergren. Upper bounds on the size of obstructions and intertwines. J. Comb. Theory, Ser. B, 73(1):7-40, 1998. Google Scholar
  14. Frank Thomson Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787-832, 1999. Google Scholar
  15. Neil Robertson and Paul D. Seymour. Graph minors XXIII. Nash-Williams' immersion conjecture. J. Comb. Theory, Ser. B, 100(2):181-205, 2010. Google Scholar
  16. Paul D. Seymour and Robin Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217-241, 1994. Google Scholar
  17. Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender. Cutwidth I: A linear time fixed parameter algorithm. J. Algorithms, 56(1):1-24, 2005. Google Scholar
  18. Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender. Cutwidth II: Algorithms for partial w-trees of bounded degree. J. Algorithms, 56(1):25-49, 2005. Google Scholar
  19. Robin Thomas. A Menger-like property of tree-width: The finite case. J. Comb. Theory, Ser. B, 48(1):67-76, 1990. Google Scholar
  20. Paul Wollan. The structure of graphs not admitting a fixed immersion. J. Comb. Theory, Ser. B, 110:47-66, 2015. Google Scholar
  21. Mihalis Yannakakis. A polynomial algorithm for the min-cut linear arrangement of trees. J. ACM, 32(4):950-988, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact