Search Results

Documents authored by Uitto, Jara

Document
DOI: 10.4230/LIPIcs.DISC.2023.11
Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem

Authors: Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
In this work, we present a constant-round algorithm for the 2-ruling set problem in the Congested Clique model. As a direct consequence, we obtain a constant round algorithm in the MPC model with linear space-per-machine and optimal total space. Our results improve on the O(log log log n)-round algorithm by [HPS, DISC'14] and the O(log log Δ)-round algorithm by [GGKMR, PODC'18]. Our techniques can also be applied to the semi-streaming model to obtain an O(1)-pass algorithm. Our main technical contribution is a novel sampling procedure that returns a small subgraph such that almost all nodes in the input graph are adjacent to the sampled subgraph. An MIS on the sampled subgraph provides a 2-ruling set for a large fraction of the input graph. As a technical challenge, we must handle the remaining part of the graph, which might still be relatively large. We overcome this challenge by showing useful structural properties of the remaining graph and show that running our process twice yields a 2-ruling set of the original input graph with high probability.
Cite as

Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cambus_et_al:LIPIcs.DISC.2023.11,
  author =	{Cambus, M\'{e}lanie and Kuhn, Fabian and Pai, Shreyas and Uitto, Jara},
  title =	{{Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{11:1--11:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.11},
  URN =		{urn:nbn:de:0030-drops-191378},
  doi =		{10.4230/LIPIcs.DISC.2023.11},
  annote =	{Keywords: Ruling Sets, Parallel Algorithms, Congested Clique, Massively Parallel Computing, Semi-Streaming}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.23
Conditionally Optimal Parallel Coloring of Forests

Authors: Christoph Grunau, Rustam Latypov, Yannic Maus, Shreyas Pai, and Jara Uitto

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
We show the first conditionally optimal deterministic algorithm for 3-coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in O(log log n) rounds and uses optimal global space. The best previous algorithm requires 4 colors [Ghaffari, Grunau, Jin, DISC'20] and is randomized, while our algorithm are inherently deterministic. Our main technical contribution is an O(log log n)-round algorithm to compute a partition of the forest into O(log n) ordered layers such that every node has at most two neighbors in the same or higher layers. Similar decompositions are often used in the area and we believe that this result is of independent interest. Our results also immediately yield conditionally optimal deterministic algorithms for maximal independent set and maximal matching for forests, matching the state of the art [Giliberti, Fischer, Grunau, SPAA'23]. In contrast to their solution, our algorithms are not based on derandomization, and are arguably simpler.
Cite as

Christoph Grunau, Rustam Latypov, Yannic Maus, Shreyas Pai, and Jara Uitto. Conditionally Optimal Parallel Coloring of Forests. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{grunau_et_al:LIPIcs.DISC.2023.23,
  author =	{Grunau, Christoph and Latypov, Rustam and Maus, Yannic and Pai, Shreyas and Uitto, Jara},
  title =	{{Conditionally Optimal Parallel Coloring of Forests}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{23:1--23:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.23},
  URN =		{urn:nbn:de:0030-drops-191494},
  doi =		{10.4230/LIPIcs.DISC.2023.23},
  annote =	{Keywords: massively parallel computation, coloring, forests, optimal}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.9
Exponential Speedup over Locality in MPC with Optimal Memory

Authors: Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and coloring problems. A successful line of research has been studying the complexities of LCL problems on paths/cycles, trees, and general graphs, providing many interesting results for the LOCAL model of distributed computing. In this work, we initiate the study of LCL problems in the low-space Massively Parallel Computation (MPC) model. In particular, on forests, we provide a method that, given the complexity of an LCL problem in the LOCAL model, automatically provides an exponentially faster algorithm for the low-space MPC setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the result, we emphasize that all known (conditional) lower bounds for the MPC setting are obtained by lifting lower bounds obtained in the distributed setting in tree-like networks (either forests or high girth graphs), and hence the problems that we study are challenging already on forests. Moreover, the most important technical feature of our algorithms is that they use optimal global memory, that is, memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests, this is not possible, because the given graph is already as sparse as it can be, and using optimal memory requires new solutions.
Cite as

Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Exponential Speedup over Locality in MPC with Optimal Memory. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2022.9,
  author =	{Balliu, Alkida and Brandt, Sebastian and Fischer, Manuela and Latypov, Rustam and Maus, Yannic and Olivetti, Dennis and Uitto, Jara},
  title =	{{Exponential Speedup over Locality in MPC with Optimal Memory}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.9},
  URN =		{urn:nbn:de:0030-drops-172003},
  doi =		{10.4230/LIPIcs.DISC.2022.9},
  annote =	{Keywords: Distributed computing, Locally checkable labeling problems, Trees, Massively Parallel Computation, Sublinear memory}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.15
Massively Parallel Correlation Clustering in Bounded Arboricity Graphs

Authors: Mélanie Cambus, Davin Choo, Havu Miikonen, and Jara Uitto

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Identifying clusters of similar elements in a set is a common task in data analysis. With the immense growth of data and physical limitations on single processor speed, it is necessary to find efficient parallel algorithms for clustering tasks. In this paper, we study the problem of correlation clustering in bounded arboricity graphs with respect to the Massively Parallel Computation (MPC) model. More specifically, we are given a complete graph where the edges are either positive or negative, indicating whether pairs of vertices are similar or dissimilar. The task is to partition the vertices into clusters with as few disagreements as possible. That is, we want to minimize the number of positive inter-cluster edges and negative intra-cluster edges. Consider an input graph G on n vertices such that the positive edges induce a λ-arboric graph. Our main result is a 3-approximation (in expectation) algorithm to correlation clustering that runs in 𝒪(log λ ⋅ poly(log log n)) MPC rounds in the strongly sublinear memory regime. This is obtained by combining structural properties of correlation clustering on bounded arboricity graphs with the insights of Fischer and Noever (SODA '18) on randomized greedy MIS and the PIVOT algorithm of Ailon, Charikar, and Newman (STOC '05). Combined with known graph matching algorithms, our structural property also implies an exact algorithm and algorithms with worst case (1+ε)-approximation guarantees in the special case of forests, where λ = 1.
Cite as

Mélanie Cambus, Davin Choo, Havu Miikonen, and Jara Uitto. Massively Parallel Correlation Clustering in Bounded Arboricity Graphs. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cambus_et_al:LIPIcs.DISC.2021.15,
  author =	{Cambus, M\'{e}lanie and Choo, Davin and Miikonen, Havu and Uitto, Jara},
  title =	{{Massively Parallel Correlation Clustering in Bounded Arboricity Graphs}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.15},
  URN =		{urn:nbn:de:0030-drops-148173},
  doi =		{10.4230/LIPIcs.DISC.2021.15},
  annote =	{Keywords: MPC Algorithm, Correlation Clustering, Bounded Arboricity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.31
Efficient CONGEST Algorithms for the Lovász Local Lemma

Authors: Yannic Maus and Jara Uitto

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
We present a poly log log n time randomized CONGEST algorithm for a natural class of Lovász Local Lemma (LLL) instances on constant degree graphs. This implies, among other things, that there are no LCL problems with randomized complexity between Ω(log n) and poly log log n. Furthermore, we provide extensions to the network decomposition algorithms given in the recent breakthrough by Rozhoň and Ghaffari [STOC2020] and the follow up by Ghaffari, Grunau, and Rozhoň [SODA2021]. In particular, we show how to obtain a large distance separated weak network decomposition with a negligible dependency on the range of unique identifiers.
Cite as

Yannic Maus and Jara Uitto. Efficient CONGEST Algorithms for the Lovász Local Lemma. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{maus_et_al:LIPIcs.DISC.2021.31,
  author =	{Maus, Yannic and Uitto, Jara},
  title =	{{Efficient CONGEST Algorithms for the Lov\'{a}sz Local Lemma}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{31:1--31:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.31},
  URN =		{urn:nbn:de:0030-drops-148333},
  doi =		{10.4230/LIPIcs.DISC.2021.31},
  annote =	{Keywords: distributed graph algorithms, CONGEST, Lov\'{a}sz Local Lemma, locally checkable labelings}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.50
Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees

Authors: Sebastian Brandt, Rustam Latypov, and Jara Uitto

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
We establish scalable Massively Parallel Computation (MPC) algorithms for a family of fundamental graph problems on trees. We give a general method that, for a wide range of LCL problems, turns their message passing counterparts into exponentially faster algorithms in the sublinear MPC model. In particular, we show that any LCL on trees that has a deterministic complexity of O(n) in the LOCAL model can be sped up to O(log n) (high-complexity regime) in the sublinear MPC model and similarly n^{o(1)} to O(log log n) (intermediate-complexity regime). We emphasize, that we work on bounded degree trees and all of our algorithms work in the sublinear MPC model, where local memory is O(n^δ) for δ < 1 and global memory is O(m). For the high-complexity regime, one key ingredient is a novel pointer-chain technique and analysis that allows us to solve any solvable LCL on trees with a sublinear MPC algorithm with complexity O(log n). For the intermediate-complexity regime, we adapt the approach by Chang and Pettie [FOCS'17], who gave a canonical algorithm for solving LCL problems on trees in the LOCAL model. For the special case of 3-coloring trees, which is a natural LCL problem, we provide a conditional Ω(log log n) lower bound, implying that solving LCL problems on trees with deterministic LOCAL complexity n^{o(1)} requires Θ(log log n) deterministic time in the sublinear MPC model when using a natural family of component-stable algorithms.
Cite as

Sebastian Brandt, Rustam Latypov, and Jara Uitto. Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 50:1-50:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{brandt_et_al:LIPIcs.DISC.2021.50,
  author =	{Brandt, Sebastian and Latypov, Rustam and Uitto, Jara},
  title =	{{Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{50:1--50:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.50},
  URN =		{urn:nbn:de:0030-drops-148521},
  doi =		{10.4230/LIPIcs.DISC.2021.50},
  annote =	{Keywords: Distributed computing, Locally checkable labeling problems, Trees, Massively Parallel Computation, Sublinear memory, 3-coloring}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.13
Tight Bounds for Deterministic High-Dimensional Grid Exploration

Authors: Sebastian Brandt, Julian Portmann, and Jara Uitto

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We study the problem of exploring an oriented grid with autonomous agents governed by finite automata. In the case of a 2-dimensional grid, the question how many agents are required to explore the grid, or equivalently, find a hidden treasure in the grid, is fully understood in both the synchronous and the semi-synchronous setting. For higher dimensions, Dobrev, Narayanan, Opatrny, and Pankratov [ICALP'19] showed very recently that, surprisingly, a (small) constant number of agents suffices to find the treasure, independent of the number of dimensions, thereby disproving a conjecture by Cohen, Emek, Louidor, and Uitto [SODA'17]. Dobrev et al. left as an open question whether their bounds on the number of agents can be improved. We answer this question in the affirmative for deterministic finite automata: we show that 3 synchronous and 4 semi-synchronous agents suffice to explore an n-dimensional grid for any constant n. The bounds are optimal and notably, the matching lower bounds already hold in the 2-dimensional case. Our techniques can also be used to make progress on other open questions asked by Dobrev et al.: we prove that 4 synchronous and 5 semi-synchronous agents suffice for polynomial-time exploration, and we show that, under a natural assumption, 3 synchronous and 4 semi-synchronous agents suffice to explore unoriented grids of arbitrary dimension (which, again, is tight).
Cite as

Sebastian Brandt, Julian Portmann, and Jara Uitto. Tight Bounds for Deterministic High-Dimensional Grid Exploration. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brandt_et_al:LIPIcs.DISC.2020.13,
  author =	{Brandt, Sebastian and Portmann, Julian and Uitto, Jara},
  title =	{{Tight Bounds for Deterministic High-Dimensional Grid Exploration}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.13},
  URN =		{urn:nbn:de:0030-drops-130911},
  doi =		{10.4230/LIPIcs.DISC.2020.13},
  annote =	{Keywords: Mobile agents, finite automata, grid search}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.40
Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping

Authors: Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for the stable orientation problem, which is a special case of the more general locally optimal semi-matching problem. The prior work by Czygrinow et al. (DISC 2012) finds a locally optimal semi-matching in O(Δ⁵) rounds in graphs of maximum degree Δ, which directly implies an algorithm with the same runtime for stable orientations. We improve the runtime to O(Δ⁴) for stable orientations and prove a lower bound of Ω(Δ) rounds.
Cite as

Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto. Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 40:1-40:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brandt_et_al:LIPIcs.DISC.2020.40,
  author =	{Brandt, Sebastian and Keller, Barbara and Rybicki, Joel and Suomela, Jukka and Uitto, Jara},
  title =	{{Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{40:1--40:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.40},
  URN =		{urn:nbn:de:0030-drops-131182},
  doi =		{10.4230/LIPIcs.DISC.2020.40},
  annote =	{Keywords: distributed algorithms, graph problems, semi-matching}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.12
Distributed Recoloring

Authors: Marthe Bonamy, Paul Ouvrard, Mikaël Rabie, Jukka Suomela, and Jara Uitto

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
Given two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the graph is properly colored after each step? We introduce the notion of distributed recoloring: The input graph represents a network of computers that needs to be recolored. Initially, each node is aware of its own input color and target color. The nodes can exchange messages with each other, and eventually each node has to stop and output its own recoloring schedule, indicating when and how the node changes its color. The recoloring schedules have to be globally consistent so that the graph remains properly colored at each point, and we require that adjacent nodes do not change their colors simultaneously. We are interested in the following questions: How many communication rounds are needed (in the deterministic LOCAL model of distributed computing) to find a recoloring schedule? What is the length of the recoloring schedule? And how does the picture change if we can use extra colors to make recoloring easier? The main contributions of this work are related to distributed recoloring with one extra color in the following graph classes: trees, 3-regular graphs, and toroidal grids.
Cite as

Marthe Bonamy, Paul Ouvrard, Mikaël Rabie, Jukka Suomela, and Jara Uitto. Distributed Recoloring. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.DISC.2018.12,
  author =	{Bonamy, Marthe and Ouvrard, Paul and Rabie, Mika\"{e}l and Suomela, Jukka and Uitto, Jara},
  title =	{{Distributed Recoloring}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.12},
  URN =		{urn:nbn:de:0030-drops-98012},
  doi =		{10.4230/LIPIcs.DISC.2018.12},
  annote =	{Keywords: Distributed Systems, Graph Algorithms, Local Computations}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.13
A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration

Authors: Sebastian Brandt, Jara Uitto, and Roger Wattenhofer

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
Recently, there has been a growing interest in grid exploration by agents with limited capabilities. We show that the grid cannot be explored by three semi-synchronous finite automata, answering an open question by Emek et al. [TCS'15] in the negative. In the setting we consider, time is divided into discrete steps, where in each step, an adversarially selected subset of the agents executes one look-compute-move cycle. The agents operate according to a shared finite automaton, where every agent is allowed to have a distinct initial state. The only means of communication is to sense the states of the agents sharing the same grid cell. The agents are equipped with a global compass and whenever an agent moves, the destination cell of the movement is chosen by the agent's automaton from the set of neighboring grid cells. In contrast to the four agent protocol by Emek et al., we show that three agents do not suffice for grid exploration.
Cite as

Sebastian Brandt, Jara Uitto, and Roger Wattenhofer. A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{brandt_et_al:LIPIcs.DISC.2018.13,
  author =	{Brandt, Sebastian and Uitto, Jara and Wattenhofer, Roger},
  title =	{{A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.13},
  URN =		{urn:nbn:de:0030-drops-98029},
  doi =		{10.4230/LIPIcs.DISC.2018.13},
  annote =	{Keywords: Finite automata, Graph exploration, Mobile robots}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.9
Fine-grained Lower Bounds on Cops and Robbers

Authors: Sebastian Brandt, Seth Pettie, and Jara Uitto

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Cops and Robbers is a classic pursuit-evasion game played between a group of g cops and one robber on an undirected N-vertex graph G. We prove that the complexity of deciding the winner in the game under optimal play requires Omega (N^{g-o(1)}) time on instances with O(N log^2 N) edges, conditioned on the Strong Exponential Time Hypothesis. Moreover, the problem of calculating the minimum number of cops needed to win the game is 2^{Omega (sqrt{N})}, conditioned on the weaker Exponential Time Hypothesis. Our conditional lower bound comes very close to a conditional upper bound: if Meyniel's conjecture holds then the cop number can be decided in 2^{O(sqrt{N}log N)} time. In recent years, the Strong Exponential Time Hypothesis has been used to obtain many lower bounds on classic combinatorial problems, such as graph diameter, LCS, EDIT-DISTANCE, and REGEXP matching. To our knowledge, these are the first conditional (S)ETH-hard lower bounds on a strategic game.
Cite as

Sebastian Brandt, Seth Pettie, and Jara Uitto. Fine-grained Lower Bounds on Cops and Robbers. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{brandt_et_al:LIPIcs.ESA.2018.9,
  author =	{Brandt, Sebastian and Pettie, Seth and Uitto, Jara},
  title =	{{Fine-grained Lower Bounds on Cops and Robbers}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.9},
  URN =		{urn:nbn:de:0030-drops-94725},
  doi =		{10.4230/LIPIcs.ESA.2018.9},
  annote =	{Keywords: Cops and Robbers}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.19
Improved Distributed Degree Splitting and Edge Coloring

Authors: Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discrepancy. The directed variant of the problem requires orienting the edges such that each node has almost the same number of incoming and outgoing edges, again up to a small additive discrepancy. We present deterministic distributed algorithms for both variants, which improve on their counterparts presented by Ghaffari and Su [SODA'17]: our algorithms are significantly simpler and faster, and have a much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for (2+o(1))Delta-edge-coloring, improving on that of Ghaffari and Su.
Cite as

Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto. Improved Distributed Degree Splitting and Edge Coloring. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2017.19,
  author =	{Ghaffari, Mohsen and Hirvonen, Juho and Kuhn, Fabian and Maus, Yannic and Suomela, Jukka and Uitto, Jara},
  title =	{{Improved Distributed Degree Splitting and Edge Coloring}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.19},
  URN =		{urn:nbn:de:0030-drops-79794},
  doi =		{10.4230/LIPIcs.DISC.2017.19},
  annote =	{Keywords: Distributed Graph Algorithms, Degree Splitting, Edge Coloring, Discrepancy}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.82
A Tight Lower Bound for the Capture Time of the Cops and Robbers Game

Authors: Sebastian Brandt, Yuval Emek, Jara Uitto, and Roger Wattenhofer

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
For the game of Cops and Robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O(n) time, and that there exist graphs in which this capture time is tight. When k >= 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O(n^{k + 1}), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be improved. In this paper, the question of Bonato and Nowakowski is answered on the negative, proving that the O(n^{k + 1}) bound is asymptotically tight for any constant k >= 2. This yields a surprising gap in the capture time complexities between the 1-cop and the 2-cop cases.
Cite as

Sebastian Brandt, Yuval Emek, Jara Uitto, and Roger Wattenhofer. A Tight Lower Bound for the Capture Time of the Cops and Robbers Game. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 82:1-82:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{brandt_et_al:LIPIcs.ICALP.2017.82,
  author =	{Brandt, Sebastian and Emek, Yuval and Uitto, Jara and Wattenhofer, Roger},
  title =	{{A Tight Lower Bound for the Capture Time of the Cops and Robbers Game}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{82:1--82:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.82},
  URN =		{urn:nbn:de:0030-drops-74134},
  doi =		{10.4230/LIPIcs.ICALP.2017.82},
  annote =	{Keywords: cops and robbers, capture time, lower bound}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.9
Overcoming Obstacles with Ants

Authors: Tobias Langner, Barbara Keller, Jara Uitto, and Roger Wattenhofer

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Consider a group of mobile finite automata, referred to as agents, located in the origin of an infinite grid. The grid is occupied by obstacles, i.e., sets of cells that can not be entered by the agents. In every step, an agent can sense the states of the co-located agents and is allowed to move to any neighboring cell of the grid not blocked by an obstacle. We assume that the circumference of each obstacle is finite but allow the number of obstacles to be unbounded. The task of the agents is to cooperatively find a treasure, hidden in the grid by an adversary. In this work, we show how the agents can utilize their simple means of communication and their constant memory to systematically explore the grid and to locate the treasure in finite time. As integral part of the agents' behavior, we present a method that allows a group of six agents to follow a straight line, even if the line is partially obstructed by obstacles, and to discover all free cells along this line. In total, our search protocol requires nine agents.
Cite as

Tobias Langner, Barbara Keller, Jara Uitto, and Roger Wattenhofer. Overcoming Obstacles with Ants. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{langner_et_al:LIPIcs.OPODIS.2015.9,
  author =	{Langner, Tobias and Keller, Barbara and Uitto, Jara and Wattenhofer, Roger},
  title =	{{Overcoming Obstacles with Ants}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.9},
  URN =		{urn:nbn:de:0030-drops-66005},
  doi =		{10.4230/LIPIcs.OPODIS.2015.9},
  annote =	{Keywords: Mobile agents, algorithms, treasure search}
}
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