DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2016.38

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

Authors: Frederik Garbe and Richard Mycroft

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{garbe_et_al:LIPIcs.STACS.2016.38,
  author =	{Garbe, Frederik and Mycroft, Richard},
  title =	{{The Complexity of the Hamilton Cycle Problem in Hypergraphs of High Minimum Codegree}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{38:1--38:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.38},
  URN =		{urn:nbn:de:0030-drops-57392},
  doi =		{10.4230/LIPIcs.STACS.2016.38},
  annote =	{Keywords: Hamilton cycles, hypergraphs, graph algorithms}
}

Search Results

Documents authored by Garbe, Frederik

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

Abstract

Cite as

Thanks for your feedback!

Could not send message