DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2023.19

Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations

Authors: Noy Biton, Reut Levi, and Moti Medina

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract

We study the problem of finding a Hamiltonian cycle under the promise that the input graph has a minimum degree of at least n/2, where n denotes the number of vertices in the graph. The classical theorem of Dirac states that such graphs (a.k.a. Dirac graphs) are Hamiltonian, i.e., contain a Hamiltonian cycle. Moreover, finding a Hamiltonian cycle in Dirac graphs can be done in polynomial time in the classical centralized model. This paper presents a randomized distributed CONGEST algorithm that finds w.h.p. a Hamiltonian cycle (as well as maximum matching) within O(log n) rounds under the promise that the input graph is a Dirac graph. This upper bound is in contrast to general graphs in which both the decision and search variants of Hamiltonicity require Ω̃(n²) rounds, as shown by Bachrach et al. [PODC'19]. In addition, we consider two generalizations of Dirac graphs: Ore graphs and Rahman-Kaykobad graphs [IPL'05]. In Ore graphs, the sum of the degrees of every pair of non-adjacent vertices is at least n, and in Rahman-Kaykobad graphs, the sum of the degrees of every pair of non-adjacent vertices plus their distance is at least n+1. We show how our algorithm for Dirac graphs can be adapted to work for these more general families of graphs.

Cite as

Noy Biton, Reut Levi, and Moti Medina. Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{biton_et_al:LIPIcs.MFCS.2023.19,
  author =	{Biton, Noy and Levi, Reut and Medina, Moti},
  title =	{{Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.19},
  URN =		{urn:nbn:de:0030-drops-185534},
  doi =		{10.4230/LIPIcs.MFCS.2023.19},
  annote =	{Keywords: the CONGEST model, Hamiltonian Path, Hamiltonian Cycle, Dirac graphs, Ore graphs, graph-algorithms}
}

Search Results

Documents authored by Biton, Noy

Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations

Abstract

Cite as

Thanks for your feedback!

Could not send message