Document Open Access Logo

Contracting to a Longest Path in H-Free Graphs

Authors Walter Kern, Daniël Paulusma

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2020.22.pdf
  • Filesize: 0.7 MB
  • 18 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • dichotomy
  • edge contraction
  • path
  • cycle
  • H-free graph

Metrics

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

Abstract

The Path Contraction problem has as input a graph G and an integer k and is to decide if G can be modified to the k-vertex path P_k by a sequence of edge contractions. A graph G is H-free for some graph H if G does not contain H as an induced subgraph. The Path Contraction problem restricted to H-free graphs is known to be NP-complete if H = claw or H = P₆ and polynomial-time solvable if H = P₅. We first settle the complexity of Path Contraction on H-free graphs for every H by developing a common technique. We then compare our classification with a (new) classification of the complexity of the problem Long Induced Path, which is to decide for a given integer k, if a given graph can be modified to P_k by a sequence of vertex deletions. Finally, we prove that the complexity classifications of Path Contraction and Cycle Contraction for H-free graphs do not coincide. The latter problem, which has not been fully classified for H-free graphs yet, is to decide if for some given integer k, a given graph contains the k-vertex cycle C_k as a contraction.

Cite As Get BibTex

Walter Kern and Daniël Paulusma. Contracting to a Longest Path in H-Free Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.22

Author Details

Walter Kern
  • Department of Applied Mathematics, University of Twente, The Netherlands
Daniël Paulusma
  • Department of Computer Science, Durham University, UK

Funding

  • Paulusma, Daniël: supported by The Leverhulme Trust (RPG-2016-258).

References

  1. Akanksha Agrawal, Fedor Fomin, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale. Path contraction faster than 2ⁿ. Proc. ICALP 2019, LIPIcs, 132:11:1-11:13, 2019. Google Scholar
  2. Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh, and Prafullkumar Tale. Paths to trees and cacti. Proc. CIAC 2017, LNCS, 10236:31-42, 2017. Google Scholar
  3. Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Split contraction: The untold story. ACM Transactions on Computation Theory, 11:18:1-18:22, 2019. Google Scholar
  4. Akanksha Agrawal, Saket Saurabh, and Prafullkumar Tale. On the parameterized complexity of contraction to generalization of trees. Theory of Computing Systems, 63:587-614, 2019. Google Scholar
  5. Rémy Belmonte, Petr A. Golovach, Pim van 't Hof, and Daniël Paulusma. Parameterized complexity of three edge contraction problems with degree constraints. Acta Informatica, 51:473-497, 2014. Google Scholar
  6. Alan A. Bertossi. The edge Hamiltonian path problem is NP-complete. Information Processing Letters, 13:157-159, 1981. Google Scholar
  7. D. Blum. Circularity of graphs. Virginia Polytechnic Institute and State University, 1982. Google Scholar
  8. A. E. Brouwer and Henk Jan Veldman. Contractibility and NP-completeness. Journal of Graph Theory, 11:71-79, 1987. Google Scholar
  9. Leizhen Cai and Chengwei Guo. Contracting few edges to remove forbidden induced subgraphs. Proc. IPEC 2013, LNCS, 8246:97-109, 2013. Google Scholar
  10. Maria Chudnovsky. The structure of bull-free graphs II and III - A summary. Journal of Combinatorial Theory, Series B, 102:252-282, 2012. Google Scholar
  11. Maria Chudnovsky and Paul D. Seymour. The structure of claw-free graphs. Surveys in Combinatorics, London Mathematical Society Lecture Note Series, 327:153-171, 2005. Google Scholar
  12. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33:125-150, 2000. Google Scholar
  13. Konrad K. Dabrowski, Matthew Johnson, and Daniël Paulusma. Clique-width for hereditary graph classes. Proc. BCC 2019, London Mathematical Society Lecture Note Series, 456:1-56, 2019. Google Scholar
  14. Konrad K. Dabrowski and Daniël Paulusma. Contracting bipartite graphs to paths and cycles. Information Processing Letters, 127:37-42, 2017. Google Scholar
  15. David Eppstein. Finding large clique minors is hard. Journal of Graph Algorithms and Applications, 13:197-204, 2009. Google Scholar
  16. Jirí Fiala, Marcin Kamiński, and Daniël Paulusma. A note on contracting claw-free graphs. Discrete Mathematics & Theoretical Computer Science, 15:223-232, 2013. Google Scholar
  17. Fedor Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, and Meirav Zehavi. Computation of hadwiger number and related contraction problems: Tight lower bounds. Proc. ICALP 2020, LIPCcs, 168:49:1-49:18, 2020. Google Scholar
  18. M. R. Garey, David S. Johnson, and Robert Endre Tarjan. The planar hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5:704-714, 1976. Google Scholar
  19. Michael R. Garey and David S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, 32:826-834, 1977. Google Scholar
  20. Michael Randolph Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979. Google Scholar
  21. Fanica Gavril. Algorithms for maximum weight induced paths. Information Processing Letters, 81:203-208, 2002. Google Scholar
  22. Petr A. Golovach, Matthew Johnson, Daniël Paulusma, and Jian Song. A survey on the computational complexity of coloring graphs with forbidden subgraphs. Journal of Graph Theory, 84:331-363, 2017. Google Scholar
  23. Petr A. Golovach, Pim van 't Hof, and Daniël Paulusma. Obtaining planarity by contracting few edges. Theoretical Computer Science, 476:38-46, 2013. Google Scholar
  24. Sylvain Guillemot and Dániel Marx. A faster FPT algorithm for bipartite contraction. Information Processing Letters, 113:906-912, 2013. Google Scholar
  25. Yi-Lu Guo, Chin-Wen Ho, and Ming-Tat Ko. The longest path problem on distance-hereditary graphs. Advances in Intelligent Systems and Applications, 1:69-77, 2013. Google Scholar
  26. Richard Hammack. Cyclicity of graphs. Journal of Graph Theory, 32:160-170, 1999. Google Scholar
  27. Richard Hammack. A note on the complexity of computing cyclicity. Ars Combinatoria, 63, 2002. Google Scholar
  28. Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque, Daniel Lokshtanov, and Christophe Paul. Contracting graphs to paths and trees. Algorithmica, 68:109-132, 2014. Google Scholar
  29. Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque, and Christophe Paul. Contracting chordal graphs and bipartite graphs to paths and trees. Discrete Applied Mathematics, 164:444-449, 2014. Google Scholar
  30. Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, and Christophe Paul. Obtaining a bipartite graph by contracting few edges. SIAM Journal on Discrete Mathematics, 27:2143-2156, 2013. Google Scholar
  31. Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, and Gerhard J. Woeginger. Domination when the stars are out. ACM Transactions on Algorithms, 15:25:1-25:90, 2019. Google Scholar
  32. Cornelis Hoede and Henk Jan Veldman. On characterization of hamiltonian graphs. Journal of Combinatorial Theory, Series B, 25:47-53, 1978. Google Scholar
  33. Cornelis Hoede and Henk Jan Veldman. Contraction theorems in hamiltonian graph theory. Discrete Mathematics, 34:61-67, 1981. Google Scholar
  34. John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2:225-231, 1973. Google Scholar
  35. Kyriaki Ioannidou, George B. Mertzios, and Stavros D. Nikolopoulos. The longest path problem has a polynomial solution on interval graphs. Algorithmica, 61:320-341, 2011. Google Scholar
  36. Kyriaki Ioannidou and Stavros D. Nikolopoulos. The longest path problem is polynomial on cocomparability graphs. Algorithmica, 65:177-205, 2013. Google Scholar
  37. Tetsuya Ishizeki, Yota Otachi, and Koichi Yamazaki. An improved algorithm for the longest induced path problem on k-chordal graphs. Discrete Applied Mathematics, 156:3057-3059, 2008. Google Scholar
  38. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Mim-width I. Induced path problems. Discrete Applied Mathematics, 278:153-168, 2020. Google Scholar
  39. Matthew Johnson, Giacomo Paesani, and Daniël Paulusma. Connected Vertex Cover for (sP₁+P₅)-free graphs. Algorithmica, 82:20-40, 2020. Google Scholar
  40. Dieter Kratsch, Haiko Müller, and Ioan Todinca. Feedback vertex set and longest induced path on AT-free graphs. Proc. WG 2003, LNCS, 2880:309-321, 2003. Google Scholar
  41. Asaf Levin, Daniël Paulusma, and Gerhard J. Woeginger. The computational complexity of graph contractions I: polynomially solvable and NP-complete cases. Networks, 51:178-189, 2008. Google Scholar
  42. Asaf Levin, Daniël Paulusma, and Gerhard J. Woeginger. The computational complexity of graph contractions II: two tough polynomially solvable cases. Networks, 52:32-56, 2008. Google Scholar
  43. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. On the hardness of eliminating small induced subgraphs by contracting edges. Proc. IPEC 2013, LNCS, 8246:243-254, 2013. Google Scholar
  44. Barnaby Martin and Daniël Paulusma. The computational complexity of disconnected cut and 2K₂-partition. Journal of Combinatorial Theory, Series B, 111:17-37, 2015. Google Scholar
  45. Dániel Marx, Barry O'Sullivan, and Igor Razgon. Finding small separators in linear time via treewidth reduction. ACM Transactions on Algorithms, 9:30:1-30:35, 2013. Google Scholar
  46. George B. Mertzios and Ivona Bezáková. Computing and counting longest paths on circular-arc graphs in polynomial time. Discrete Applied Mathematics, 164:383-399, 2014. Google Scholar
  47. George B. Mertzios and Derek G. Corneil. A simple polynomial algorithm for the longest path problem on cocomparability graphs. SIAM Journal on Discrete Mathematics, 26:940-963, 2012. Google Scholar
  48. Haiko Müller. Hamiltonian circuits in chordal bipartite graphs. Discrete Mathematics, 156:291-298, 1996. Google Scholar
  49. Bert Randerath and Ingo Schiermeyer. Vertex colouring and forbidden subgraphs - A survey. Graphs and Combinatorics, 20:1-40, 2004. Google Scholar
  50. Neil Robertson and Paul D. Seymour. Graph minors .xiii. the disjoint paths problem. Journal of Combinatorial Theory, Series B, 63:65-110, 1995. Google Scholar
  51. Bin Sheng and Yuefang Sun. An improved linear kernel for the cycle contraction problem. Information Processing Letters, 149:14-18, 2019. Google Scholar
  52. Ryuhei Uehara and Yushi Uno. On computing longest paths in small graph classes. International Journal of Foundations of Computer Science, 18:911-930, 2007. Google Scholar
  53. Ryuhei Uehara and Gabriel Valiente. Linear structure of bipartite permutation graphs and the longest path problem. Information Processing Letters, 103:71-77, 2007. Google Scholar
  54. Pim van 't Hof, Marcin Kamiński, Daniël Paulusma, Stefan Szeider, and Dimitrios M. Thilikos. On graph contractions and induced minors. Discrete Applied Mathematics, 160:799-809, 2012. Google Scholar
  55. Pim van 't Hof, Daniël Paulusma, and Gerhard J. Woeginger. Partitioning graphs into connected parts. Theoretical Computer Science, 410:4834-4843, 2009. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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