Projects per year
Abstract
We consider the complexity of the Hamilton cycle decision problem when restricted to kuniform hypergraphs H of high minimum codegree delta(H). We show that for tight Hamilton cycles this problem is NPhard even when restricted to kuniform 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 polynomialtime algorithm which, for a sufficiently small constant epsilon > 0, determines whether or not a 4uniform hypergraph H on n vertices with delta(H) >= n/2  epsilon * n contains a Hamilton 2cycle. 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 4uniform hypergraphs H on n vertices with delta(H) >= n/2  epsilon * n which do not contain a Hamilton 2cycle; this may be of independent interest. As an additional corollary of this characterisation, we obtain an exact Diractype bound for the existence of a Hamilton 2cycle in a large 4uniform hypergraph.
Original language  English 

Title of host publication  33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) 
Editors  Nicolas Ollinger, Heribert Vollmer 
Place of Publication  Dagstuhl, Germany 
Publisher  Schloss Dagstuhl 
Pages  113 
Number of pages  13 
Volume  47 
ISBN (Electronic)  9783959770019 
DOIs  
Publication status  Published  16 Feb 2016 
Publication series
Name  Leibniz International Proceedings in Informatics (LIPIcs) 

Publisher  Schloss DagstuhlLeibnizZentrum fuer Informatik 
Volume  47 
ISSN (Electronic)  18688969 
Keywords
 Hamilton cycles
 hypergraphs
 graph algorithms
Fingerprint
Dive into the research topics of 'The Complexity of the Hamilton Cycle Problem in Hypergraphs of High Minimum Codegree'. Together they form a unique fingerprint.Projects
 1 Finished

Embeddings in hypergraphs
Engineering & Physical Science Research Council
30/03/15 → 29/03/17
Project: Research Councils