Document Open Access Logo

Cyclability in Graph Classes

Authors Christophe Crespelle, Carl Feghali, Petr A. Golovach

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.16.pdf
  • Filesize: 0.55 MB
  • 13 pages

Document Identifiers

Author Details

Christophe Crespelle
  • Department of Informatics, University of Bergen, Norway
Carl Feghali
  • Department of Informatics, University of Bergen, Norway
Petr A. Golovach
  • Department of Informatics, University of Bergen, Norway

Funding

The research leading to these results has received funding from the Research Council of Norway via the projects "CLASSIS" and "MULTIVAL", and from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 749022.

Cite AsGet BibTex

Christophe Crespelle, Carl Feghali, and Petr A. Golovach. Cyclability in Graph Classes. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.16

Abstract

A subset T subseteq V(G) of vertices of a graph G is said to be cyclable if G has a cycle C containing every vertex of T, and for a positive integer k, a graph G is k-cyclable if every subset of vertices of G of size at most k is cyclable. The Terminal Cyclability problem asks, given a graph G and a set T of vertices, whether T is cyclable, and the k-Cyclability problem asks, given a graph G and a positive integer k, whether G is k-cyclable. These problems are generalizations of the classical Hamiltonian Cycle problem. We initiate the study of these problems for graph classes that admit polynomial algorithms for Hamiltonian Cycle. We show that Terminal Cyclability can be solved in linear time for interval graphs, bipartite permutation graphs and cographs. Moreover, we construct certifying algorithms that either produce a solution, that is, a cycle, or output a graph separator that certifies a no-answer. We use these results to show that k-Cyclability can be solved in polynomial time when restricted to the aforementioned graph classes.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Cyclability
  • interval graphs
  • bipartite permutation graphs
  • cographs

Metrics

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

References

  1. Eyad Alkassar, Sascha Böhme, Kurt Mehlhorn, and Christine Rizkallah. A Framework for the Verification of Certifying Computations. J. Autom. Reasoning, 52(3):241-273, 2014. URL: https://doi.org/10.1007/s10817-013-9289-2.
  2. Douglas Bauer, Hajo Broersma, and Edward F. Schmeichel. Toughness in Graphs - A Survey. Graphs and Combinatorics, 22(1):1-35, 2006. URL: https://doi.org/10.1007/s00373-006-0649-0.
  3. Andreas Björklund, Thore Husfeldt, and Nina Taslaman. Shortest cycle through specified elements. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1747-1753. SIAM, 2012. URL: http://portal.acm.org/citation.cfm?id=2095255&CFID=63838676&CFTOKEN=79617016, URL: https://doi.org/10.1137/1.9781611973099.139.
  4. Kellogg S. Booth and George S. Lueker. Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms. J. Comput. Syst. Sci., 13(3):335-379, 1976. URL: https://doi.org/10.1016/S0022-0000(76)80045-1.
  5. Andreas Brandstädt and Dieter Kratsch. On the restriction of some NP-complete graph problems to permutation graphs. In Fundamentals of Computation Theory, FCT '85, Cottbus, GDR, September 9-13, 1985, volume 199 of Lecture Notes in Computer Science, pages 53-62. Springer, 1985. URL: https://doi.org/10.1007/BFb0028791.
  6. Andreas Brandstadt, Van Bang Le, and Jeremy P. Spinrad. Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. URL: https://doi.org/10.1137/1.9780898719796.
  7. Hajo Broersma, Jirí Fiala, Petr A. Golovach, Tomás Kaiser, Daniël Paulusma, and Andrzej Proskurowski. Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Journal of Graph Theory, 79(4):282-299, 2015. URL: https://doi.org/10.1002/jgt.21832.
  8. Maw-Shang Chang, Sheng-Lung Peng, and Jenn-Liang Liaw. Deferred-query: An efficient approach for some problems on interval graphs. Networks, 34(1):1-10, 1999. URL: https://doi.org/10.1002/(SICI)1097-0037(199908)34:1<1::AID-NET1>3.0.CO;2-C.
  9. Vasek Chvátal. Tough graphs and hamiltonian circuits. Discrete Mathematics, 5(3):215-228, 1973. URL: https://doi.org/10.1016/0012-365X(73)90138-6.
  10. Derek G. Corneil, Barnaby Dalton, and Michel Habib. LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs. SIAM J. Comput., 42(3):792-807, 2013. URL: https://doi.org/10.1137/11083856X.
  11. Derek G. Corneil, H. Lerchs, and L. Stewart Burlingham. Complement reducible graphs. Discrete Applied Mathematics, 3(3):163-174, 1981. URL: https://doi.org/10.1016/0166-218X(81)90013-5.
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  13. Peter Damaschke. Paths in interval graphs and circular arc graphs. Discrete Mathematics, 112(1-3):49-64, 1993. URL: https://doi.org/10.1016/0012-365X(93)90223-G.
  14. Peter Damaschke, Jitender S. Deogun, Dieter Kratsch, and George Steiner. Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm. Order, 8(4):383-391, 1991. URL: https://doi.org/10.1007/BF00571188.
  15. Jitender S. Deogun, Dieter Kratsch, and George Steiner. 1-Tough cocomparability graphs are hamiltonian. Discrete Mathematics, 170(1-3):99-106, 1997. URL: https://doi.org/10.1016/0012-365X(95)00359-5.
  16. Jitender S. Deogun and George Steiner. Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs. SIAM J. Comput., 23(3):520-552, 1994. URL: https://doi.org/10.1137/S0097539791200375.
  17. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  18. Gabriel Andrew Dirac. In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen. Math. Nachr., 22:61-85, 1960. URL: https://doi.org/10.1002/mana.19600220107.
  19. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  20. Petr A. Golovach, Marcin Kaminski, Spyridon Maniatis, and Dimitrios M. Thilikos. The Parameterized Complexity of Graph Cyclability. SIAM J. Discrete Math., 31(1):511-541, 2017. URL: https://doi.org/10.1137/141000014.
  21. M. C. Golumbic. Algorithmic graph theory and perfect graphs, volume 57. Elsevier, 2004. Google Scholar
  22. Ronald J. Gould. A look at cycles containing specified elements of a graph. Discrete Mathematics, 309(21):6299-6311, 2009. URL: https://doi.org/10.1016/j.disc.2008.04.017.
  23. Ruo-Wei Hung and Maw-Shang Chang. Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs^,. Theor. Comput. Sci., 341(1-3):411-440, 2005. URL: https://doi.org/10.1016/j.tcs.2005.04.009.
  24. Ruo-Wei Hung and Maw-Shang Chang. Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs. Appl. Math. Lett., 24(5):648-652, 2011. URL: https://doi.org/10.1016/j.aml.2010.11.030.
  25. H. A. Jung. On a class of posets and the corresponding comparability graphs. J. Comb. Theory, Ser. B, 24(2):125-133, 1978. URL: https://doi.org/10.1016/0095-8956(78)90013-8.
  26. J. Mark Keil. Finding Hamiltonian Circuits in Interval Graphs. Inf. Process. Lett., 20(4):201-206, 1985. URL: https://doi.org/10.1016/0020-0190(85)90050-X.
  27. Ross M. McConnell, Kurt Mehlhorn, Stefan Näher, and Pascal Schweitzer. Certifying algorithms. Computer Science Review, 5(2):119-161, 2011. URL: https://doi.org/10.1016/j.cosrev.2010.09.009.
  28. Haiko Müller. Hamiltonian circuits in chordal bipartite graphs. Discrete Mathematics, 156(1-3):291-298, 1996. URL: https://doi.org/10.1016/0012-365X(95)00057-4.
  29. Neil Robertson and Paul D. Seymour. Graph Minors .XIII. The Disjoint Paths Problem. J. Comb. Theory, Ser. B, 63(1):65-110, 1995. URL: https://doi.org/10.1006/jctb.1995.1006.
  30. Jeremy P. Spinrad, Andreas Brandstädt, and Lorna Stewart. Bipartite permutation graphs. Discrete Applied Mathematics, 18(3):279-292, 1987. URL: https://doi.org/10.1016/S0166-218X(87)80003-3.
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 Imprint Privacy Contact