Document Open Access Logo

The Complexity of the Hamilton Cycle Problem in Hypergraphs of High Minimum Codegree

Authors Frederik Garbe, Richard Mycroft

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.38.pdf
  • Filesize: 0.62 MB
  • 13 pages

Document Identifiers

Author Details

Frederik Garbe
Richard Mycroft

Cite As Get BibTex

Frederik Garbe and Richard Mycroft. The Complexity of the Hamilton Cycle Problem in Hypergraphs of High Minimum Codegree. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.38

Abstract

We consider the complexity of the Hamilton cycle decision problem when restricted to k-uniform hypergraphs H of high minimum codegree delta(H). We show that for tight Hamilton cycles this problem is NP-hard even when restricted to k-uniform hypergraphs H with delta(H) >= n/2 - C, where n is the order of H and C is a constant which depends only on k. This answers a question raised by Karpinski, Rucinski and Szymanska. Additionally we give a polynomial-time algorithm which, for a sufficiently small constant epsilon > 0, determines whether or not a 4-uniform hypergraph H on n vertices with delta(H) >= n/2 - epsilon * n contains a Hamilton 2-cycle. This demonstrates that some looser Hamilton cycles exhibit interestingly different behaviour compared to tight Hamilton cycles. A key part of the proof is a precise characterisation of all 4-uniform hypergraphs H on n vertices with delta(H) >= n/2 - epsilon * n which do not contain a Hamilton 2-cycle; this may be of independent interest. As an additional corollary of this characterisation, we obtain an exact Dirac-type bound for the existence of a Hamilton 2-cycle in a  large 4-uniform hypergraph.

Subject Classification

Keywords
  • Hamilton cycles
  • hypergraphs
  • graph algorithms

Metrics

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

References

  1. J.-C. Bermond, A. Germa, M.-C. Heydemann, and D. Sotteau. Hypergraphes hamiltoniens. In Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 of Colloq. Internat. CNRS, pages 39-43. CNRS, Paris, 1978. Google Scholar
  2. Andrzej Czygrinow and Theodore Molla. Tight codegree condition for the existence of loose Hamilton cycles in 3-graphs. SIAM Journal on Discrete Mathematics, 28(1):67-76, 2014. URL: http://dx.doi.org/10.1137/120890417.
  3. Elias Dahlhaus, Peter Hajnal, and Marek Karpiński. On the parallel complexity of Hamiltonian cycle and matching problem on dense graphs. Journal of Algorithms, 15:367-384, 1993. Google Scholar
  4. G. A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, 2:69-81, 1952. Google Scholar
  5. M.R. Garey, D.S. Johnson, and L.Stockmeyer. Some simplified np-complete graph problems. Theoretical Computer Science, 1:237-267, 1976. Google Scholar
  6. Hiep Hàn and Mathias Schacht. Dirac-type results for loose Hamilton cycles in uniform hypergraphs. Journal of Combinatorial Theory, Series B, 100(3):332-346, 2010. URL: http://dx.doi.org/10.1016/j.jctb.2009.10.002.
  7. Jie Han. Decision problem for perfect matchings in dense k-uniform hypergraphs. arXiv:1409.5931. Google Scholar
  8. Jie Han and Yi Zhao. Minimum codegree threshold for Hamilton 𝓁-cycles in k-uniform hypergraphs. Journal of Combinatorial Theory, Series A, 132(0):194-223, 2015. URL: http://dx.doi.org/10.1016/j.jcta.2015.01.004.
  9. Richard Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, New York: Plenum:85-103, 1972. Google Scholar
  10. Marek Karpiński, Andrzej Ruciński, and Edyta Szymańska. Computational complexity of the Hamiltonian cycle problem in dense hypergraphs. In LATIN 2010: Theoretical Informatics, 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010. Proceedings, pages 662-673, 2010. Google Scholar
  11. Peter Keevash, Fiachra Knox, and Richard Mycroft. Polynomial-time perfect matchings in dense hypergraphs. Advances in Mathematics, 269:265-334, 2014. Google Scholar
  12. Peter Keevash, Daniela Kühn, Richard Mycroft, and Deryk Osthus. Loose Hamilton cycles in hypergraphs. Discrete Mathematics, 311(7):544-559, 2011. URL: http://dx.doi.org/10.1016/j.disc.2010.11.013.
  13. Daniela Kühn, Richard Mycroft, and Deryk Osthus. Hamilton 𝓁-cycles in uniform hypergraphs. Journal of Combinatorial Theory, Series A, 117:910-927, 2010. Google Scholar
  14. Daniela Kühn and Deryk Osthus. Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree. Journal of Combinatorial Theory, Series B, 96(6):767-821, 2006. URL: http://dx.doi.org/10.1016/j.jctb.2006.02.004.
  15. Daniela Kühn and Deryk Osthus. Hamilton cycles in graphs and hypergraphs: an extremal perspective. Proceedings of the International Congress of Mathematicians 2014, Seoul, Korea, 4:381-406, 2014. Google Scholar
  16. Vojtěch Rödl and Andrzej Ruciński. Dirac-type questions for hypergraphs - a survey (or more problems for Endre to solve). In Imre Bárány, József Solymosi, and Gáábor Sági, editors, An Irregular Mind, volume 21 of Bolyai Society Mathematical Studies, pages 561-590. Springer Berlin Heidelberg, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14444-8_16.
  17. Vojtěch Rödl, Andrzej Ruciński, and Endre Szemerédi. A Dirac-type theorem for 3-uniform hypergraphs. Combinatorics, Probability and Computing, 15(1-2):229-251, 2006. URL: http://dx.doi.org/10.1017/S0963548305007042.
  18. Vojtěch Rödl, Andrzej Ruciński, and Endre Szemerédi. An approximate Dirac-type theorem for k-uniform hypergraphs. Combinatorica, 28(2):229-260, 2008. URL: http://dx.doi.org/10.1007/s00493-008-2295-z.
  19. Vojtěch Rödl, Andrzej Ruciński, and Endre Szemerédi. Dirac-type conditions for Hamiltonian paths and cycles in 3-uniform hypergraphs. Advances in Mathematics, 227:1225-1299, 2011. Google Scholar
  20. Edyta Szymańska. The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree. European Journal of Combinatorics, 34(3):632-646, 2013. URL: http://dx.doi.org/10.1016/j.ejc.2011.12.009.
  21. Yi Zhao. Recent advances on Dirac-type problems for hypergraphs. arXiv:1508.06170. 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