Arrow Research search

Author name cluster

Reut Levi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers
1 author row

Possible papers

4

MFCS Conference 2023 Conference Paper

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

  • Noy Biton
  • Reut Levi
  • Moti Medina

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.

Details

SODA Conference 2018 Conference Paper

Testing bounded arboricity

  • Talya Eden
  • Reut Levi
  • Dana Ron

In this paper we consider the problem of testing whether a graph has bounded arboricity. The family of graphs with bounded arboricity includes, among others, bounded-degree graphs, all minor-closed graph classes (e. g. planar graphs, graphs with bounded treewidth) and randomly generated preferential attachment graphs. Graphs with bounded arboricity have been studied extensively in the past, in particular since for many problems they allow for much more efficient algorithms and/or better approximation ratios. We present a tolerant tester in the sparse-graphs model. The sparse-graphs model allows access to degree queries and neighbor queries, and the distance is defined with respect to the actual number of edges. More specifically, our algorithm distinguishes between graphs that are e-close to having arboricity α and graphs that c · ∊ -far from having arboricity 3 α, where c is an absolute small constant. The query complexity and running time of the algorithm are 1 where n denotes the number of vertices and m denotes the number of edges. In terms of the dependence on n and m this bound is optimal up to poly-logarithmic factors since queries are necessary (and the arboricity of a graph is always. We leave it as an open question whether the dependence on 1/ ∊ can be improved from quasi-polynomial to polynomial. Our techniques include an efficient local simulation for approximating the outcome of a global (almost) forest-decomposition algorithm as well as a tailored procedure of edge sampling.

Details