2026-07-23T19:06:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5739 2024-03-06T10:36:58Z ddc:004 open_access

The Complexity of the Hamilton Cycle Problem in Hypergraphs of High Minimum Codegree Garbe, Frederik Mycroft, Richard Hamilton cycles hypergraphs graph algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Frederik Garbe and Richard Mycroft 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.38 urn:nbn:de:0030-drops-57392 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.38 eng https://creativecommons.org/licenses/by/3.0/legalcode