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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Colleges, School and Institutes

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.

Details

Original languageEnglish
Title of host publication33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
EditorsNicolas Ollinger, Heribert Vollmer
Publication statusPublished - 16 Feb 2016

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume47
ISSN (Electronic)1868-8969

Keywords

  • Hamilton cycles, hypergraphs, graph algorithms