Document Open Access Logo

The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs

Authors Thomas Bellitto, Shaohua Li, Karolina Okrasa , Marcin Pilipczuk, Manuel Sorge

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.59.pdf
  • Filesize: 0.77 MB
  • 15 pages

Document Identifiers

Author Details

Thomas Bellitto
  • Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
Shaohua Li
  • Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
Karolina Okrasa
  • Faculty of the Mathematics and Information Science, Warsaw University of Technology, Poland
  • Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
Marcin Pilipczuk
  • Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
Manuel Sorge
  • Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland

Funding

This research is part of a project that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement 714704.

Cite As Get BibTex

Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, and Manuel Sorge. The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.59

Abstract

The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics.
We initiate the study of fundamental connectivity problems from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth of finding a properly colored Hamiltonian cycle in an edge-colored graph; properly colored walks in edge-colored graphs is one of the most studied special cases of compatible walks in forbidden-transition graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Graph algorithms
  • fixed-parameter tractability
  • parameterized complexity

Metrics

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

Related Versions

References

  1. Abdelfattah Abouelaoualim, Kinkar Chandra Das, Luérbio Faria, Yannis Manoussakis, Carlos A. J. Martinhon, and Rachid Saad. Paths and trails in edge-colored graphs. Theoretical Computer Science, 409(3):497-510, 2008. URL: https://doi.org/10.1016/j.tcs.2008.09.021.
  2. Mustaq Ahmed and Anna Lubiw. Shortest paths avoiding forbidden subpaths. In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pages 63-74, 2009. URL: https://doi.org/10.4230/LIPIcs.STACS.2009.1831.
  3. Jørgen Bang-Jensen, Thomas Bellitto, William Lochet, and Anders Yeo. The directed 2-linkage problem with length constraints. Theoretical Computer Science, 814:69-73, 2020. URL: https://doi.org/10.1016/j.tcs.2020.01.012.
  4. Jørgen Bang-Jensen, Thomas Bellitto, and Anders Yeo. Supereulerian 2-edge-coloured graphs. Technical report, arXiv:2004.01955 [math.CO], 2020. URL: http://arxiv.org/abs/2004.01955.
  5. Jørgen Bang-Jensen and Gregory Z. Gutin. Digraphs - Theory, Algorithms and Applications. Springer, 2009. Google Scholar
  6. Thomas Bellitto. Separating codes and traffic monitoring. Theoretical Computer Science, 717:73-85, 2018. Selected papers presented at the 11th International Conference on Algorithmic Aspects of Information and Management (AAIM 2016). URL: https://doi.org/10.1016/j.tcs.2017.03.044.
  7. Thomas Bellitto and Benjamin Bergougnoux. On minimum connecting transition sets in graphs. In Andreas Brandstädt, Ekkehard Köhler, and Klaus Meer, editors, Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018), volume 11159 of Lecture Notes in Computer Science, pages 40-51. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-00256-5_4.
  8. Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, and Manuel Sorge. The complexity of connectivity problems in forbidden-transition graphs and edge-colored graphs. Technical report, arXiv:2009.12892 [cs.DS], 2020. URL: http://arxiv.org/abs/2009.12892.
  9. Kristóf Bérczi and Yusuke Kobayashi. The directed disjoint shortest paths problem. In Kirk Pruhs and Christian Sohler, editors, Proceedings of the 25th Annual European Symposium on Algorithms (ESA 2017), volume 87 of LIPIcs, pages 13:1-13:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.13.
  10. Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V Fomin. Finding detours is fixed-parameter tractable. SIAM Journal on Discrete Mathematics, 33(4):2326-2345, 2019. Google Scholar
  11. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation, 243:86-111, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.008.
  12. Alejandro Contreras-Balbuena, Hortensia Galeana-Sánchez, and Ilan A. Goldfeder. A new sufficient condition for the existence of alternating hamiltonian cycles in 2-edge-colored multigraphs. Discrete Applied Mathematics, 229:55-63, 2017. URL: https://doi.org/10.1016/j.dam.2017.04.033.
  13. Alejandro Contreras-Balbuena, Hortensia Galeana-Sánchez, and Ilan A. Goldfeder. Alternating hamiltonian cycles in 2-edge-colored multigraphs. Discrete Mathematics and Theoretical Computer Science, 21(1), 2019. URL: http://dmtcs.episciences.org/5564.
  14. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  15. Dietmar Dorninger. Hamiltonian circuits determining the order of chromosomes. Discrete Applied Mathematics, 50(2):159-168, 1994. URL: https://doi.org/10.1016/0166-218X(92)00171-H.
  16. Zdenek Dvorák. Two-factors in orientated graphs with forbidden transitions. Discrete Mathematics, 309(1):104-112, 2009. URL: https://doi.org/10.1016/j.disc.2007.12.050.
  17. Michael R. Fellows, Danny Hermelin, Frances Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1):53-61, 2009. URL: https://doi.org/10.1016/j.tcs.2008.09.065.
  18. Steven Fortune, John E. Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theor. Comput. Sci., 10:111-121, 1980. URL: https://doi.org/10.1016/0304-3975(80)90009-2.
  19. Robert Ganian, Eun Jung Kim, and Stefan Szeider. Algorithmic applications of tree-cut width. In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald Sannella, editors, Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), volume 9235 of Lecture Notes in Computer Science, pages 348-360. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48054-0_29.
  20. Marinus Gottschau, Marcus Kaiser, and Clara Waldmann. The undirected two disjoint shortest paths problem. Operations Research Letters, 47(1):70-75, 2019. URL: https://doi.org/10.1016/j.orl.2018.11.011.
  21. Laurent Gourvès, Adria Lyra, Carlos A. J. Martinhon, and Jérôme Monnot. Complexity of trails, paths and circuits in arc-colored digraphs. Discrete Applied Mathematics, 161(6):819-828, 2013. URL: https://doi.org/10.1016/j.dam.2012.10.025.
  22. Laurent Gourvès, Adria Lyra, Carlos A. J. Martinhon, Jérôme Monnot, and Fábio Protti. On s-t paths and trails in edge-colored graphs. Electronic Notes in Discrete Mathematics, 35:221-226, 2009. URL: https://doi.org/10.1016/j.endm.2009.11.037.
  23. Jerrold W. Grossman and Roland Häggkvist. Alternating cycles in edge-partitioned graphs. Journal of Combinatorial Theory, Series B, 34(1):77-81, 1983. URL: https://doi.org/10.1016/0095-8956(83)90008-4.
  24. Gregory Gutin and Eun Jung Kim. Properly coloured cycles and paths: Results and open problems. In Graph Theory, Computational Intelligence and Thought, Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday, pages 200-208, 2009. URL: https://doi.org/10.1007/978-3-642-02029-2_19.
  25. Gregory Z. Gutin, Mark Jones, Bin Sheng, Magnus Wahlström, and Anders Yeo. Chinese postman problem on edge-colored multigraphs. Discrete Applied Mathematics, 217:196-202, 2017. URL: https://doi.org/10.1016/j.dam.2016.08.005.
  26. R. Impagliazzo and R. Paturi. Complexity of k-SAT. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity (CCC 1999), pages 237-240, 1999. URL: https://doi.org/10.1109/CCC.1999.766282.
  27. R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pages 653-662, 1998. URL: https://doi.org/10.1109/SFCS.1998.743516.
  28. Mamadou Moustapha Kanté, Christian Laforest, and Benjamin Momège. Trees in graphs with conflict edges or forbidden transitions. In T.-H. Hubert Chan, Lap Chi Lau, and Luca Trevisan, editors, Proceedins of the 10th International Conference on Theory and Applications of Models of Computation (TAMC 2013), volume 7876 of Lecture Notes in Computer Science, pages 343-354. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38236-9_31.
  29. Mamadou Moustapha Kanté, Fatima Zahra Moataz, Benjamin Momège, and Nicolas Nisse. Finding paths in grids with forbidden transitions. In Ernst W. Mayr, editor, Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), volume 9224 of Lecture Notes in Computer Science, pages 154-168. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-53174-7_12.
  30. Yusuke Kobayashi and Ryo Sako. Two disjoint shortest paths problem with non-negative edge length. Operations Research Letters, 47(1):66-69, 2019. URL: https://doi.org/10.1016/j.orl.2018.11.012.
  31. Anton Kotzig. Moves without forbidden transitions in a graph. Matematický časopis, 18(1):76-80, 1968. URL: http://eudml.org/doc/33972.
  32. Ruonan Li, Hajo Broersma, Chuandong Xu, and Shenggui Zhang. Cycle extension in edge-colored complete graphs. Discret. Math., 340(6):1235-1241, 2017. URL: https://doi.org/10.1016/j.disc.2017.01.023.
  33. Ruonan Li, Hajo Broersma, and Shenggui Zhang. Properly edge-colored theta graphs in edge-colored complete graphs. Graphs and Combinatorics, 35(1):261-286, 2019. URL: https://doi.org/10.1007/s00373-018-1989-2.
  34. Dániel Marx. Can you beat treewidth? Theory of Computing, 6(1):85-112, 2010. URL: https://doi.org/10.4086/toc.2010.v006a005.
  35. Dániel Marx and Paul Wollan. Immersions in highly edge connected graphs. SIAM Journal on Discrete Mathematics, 28(1):503-520, 2014. URL: https://doi.org/10.1137/130924056.
  36. Stefan Szeider. Finding paths in graphs avoiding forbidden transitions. Discrete Applied Mathematics, 126(2-3):261-273, 2003. URL: https://doi.org/10.1016/S0166-218X(02)00251-2.
  37. Paul Wollan. The structure of graphs not admitting a fixed immersion. Journal of Combinatorial Theory, Series B, 110:47-66, 2015. Google Scholar
  38. Anders Yeo. A note on alternating cycles in edge-coloured graphs. Journal of Combinatorial Theory, Series B, 69(2):222-225, 1997. URL: https://doi.org/10.1006/jctb.1997.1728.
  39. Michal Ziobro and Marcin Pilipczuk. Finding hamiltonian cycle in graphs of bounded treewidth: Experimental evaluation. ACM Journal of Experimental Algorithmics, 24(1):2.7:1-2.7:18, 2019. URL: https://doi.org/10.1145/3368631.
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