1 Search Results for "Garbe, Frederik"

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-dev.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}
}
  • Refine by Author
  • 1 Garbe, Frederik
  • 1 Mycroft, Richard

  • Refine by Classification

  • Refine by Keyword
  • 1 Hamilton cycles
  • 1 graph algorithms
  • 1 hypergraphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

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 Imprint Privacy Contact