Document

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

We study the problem of collaborative tree exploration introduced by Fraigniaud, Gasieniec, Kowalski, and Pelc [Pierre Fraigniaud et al., 2006] where a team of k agents is tasked to collectively go through all the edges of an unknown tree as fast as possible and return to the root. Denoting by n the total number of nodes and by D the tree depth, the 𝒪(n/log(k)+D) algorithm of [Pierre Fraigniaud et al., 2006] achieves a 𝒪(k/log(k)) competitive ratio with respect to the cost of offline exploration which is at least max{{2n/k,2D}}. Brass, Cabrera-Mora, Gasparri, and Xiao [Peter Brass et al., 2011] study an alternative performance criterion, the competitive overhead with respect to the cost of offline exploration, with their 2n/k+𝒪((D+k)^k) guarantee. In this paper, we introduce "Breadth-First Depth-Next" (BFDN), a novel and simple algorithm that performs collaborative tree exploration in 2n/k+𝒪(D²log(k)) rounds, thus outperforming [Peter Brass et al., 2011] for all values of (n,D,k) and being order-optimal for trees of depth D = o(√n). Our analysis relies on a two-player game reflecting a problem of online resource allocation that could be of independent interest. We extend the guarantees of BFDN to: scenarios with limited memory and communication, adversarial setups where robots can be blocked, and exploration of classes of non-tree graphs. Finally, we provide a recursive version of BFDN with a runtime of 𝒪_𝓁(n/k^{1/𝓁}+log(k) D^{1+1/𝓁}) for parameter 𝓁 ≥ 1, thereby improving performance for trees with large depth.

Romain Cosson, Laurent Massoulié, and Laurent Viennot. Efficient Collaborative Tree Exploration with Breadth-First Depth-Next. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 14:1-14:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cosson_et_al:LIPIcs.DISC.2023.14, author = {Cosson, Romain and Massouli\'{e}, Laurent and Viennot, Laurent}, title = {{Efficient Collaborative Tree Exploration with Breadth-First Depth-Next}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {14:1--14:21}, 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.14}, URN = {urn:nbn:de:0030-drops-191409}, doi = {10.4230/LIPIcs.DISC.2023.14}, annote = {Keywords: collaborative exploration, online algorithms, trees, adversarial game, competitive analysis, robot swarms} }

Document

**Published in:** LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

The average properties of the well-known Subset Sum Problem can be studied by means of its randomised version, where we are given a target value z, random variables X_1, …, X_n, and an error parameter ε > 0, and we seek a subset of the X_is whose sum approximates z up to error ε. In this setup, it has been shown that, under mild assumptions on the distribution of the random variables, a sample of size 𝒪(log(1/ε)) suffices to obtain, with high probability, approximations for all values in [-1/2, 1/2]. Recently, this result has been rediscovered outside the algorithms community, enabling meaningful progress in other fields. In this work, we present an alternative proof for this theorem, with a more direct approach and resourcing to more elementary tools.

Arthur Carvalho Walraven Da Cunha, Francesco d'Amore, Frédéric Giroire, Hicham Lesfari, Emanuele Natale, and Laurent Viennot. Revisiting the Random Subset Sum Problem. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 37:1-37:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dacunha_et_al:LIPIcs.ESA.2023.37, author = {Da Cunha, Arthur Carvalho Walraven and d'Amore, Francesco and Giroire, Fr\'{e}d\'{e}ric and Lesfari, Hicham and Natale, Emanuele and Viennot, Laurent}, title = {{Revisiting the Random Subset Sum Problem}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {37:1--37:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.37}, URN = {urn:nbn:de:0030-drops-186905}, doi = {10.4230/LIPIcs.ESA.2023.37}, annote = {Keywords: Random subset sum, Randomised method, Subset-sum, Combinatorics} }

Document

**Published in:** LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

This paper proposes a simple algorithm for computing single-source reachability in a temporal graph under waiting-time constraints, that is when waiting at each node is bounded by some time constraints. Given a space-time representation of a temporal graph, and a source node, the algorithm computes in linear-time which nodes and temporal edges are reachable through a constrained temporal walk from the source.

Filippo Brunelli and Laurent Viennot. Computing Temporal Reachability Under Waiting-Time Constraints in Linear Time. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 4:1-4:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{brunelli_et_al:LIPIcs.SAND.2023.4, author = {Brunelli, Filippo and Viennot, Laurent}, title = {{Computing Temporal Reachability Under Waiting-Time Constraints in Linear Time}}, booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)}, pages = {4:1--4:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-275-4}, ISSN = {1868-8969}, year = {2023}, volume = {257}, editor = {Doty, David and Spirakis, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.4}, URN = {urn:nbn:de:0030-drops-179402}, doi = {10.4230/LIPIcs.SAND.2023.4}, annote = {Keywords: temporal reachability, temporal graph, temporal path, temporal walk, waiting-time constraints, restless temporal walk, linear time} }

Document

Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management

**Published in:** LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

For fixed h >= 2, we consider the task of adding to a graph G a set of weighted shortcut edges on the same vertex set, such that the length of a shortest h-hop path between any pair of vertices in the augmented graph is exactly the same as the original distance between these vertices in G. A set of shortcut edges with this property is called an exact h-hopset and may be applied in processing distance queries on graph G. In particular, a 2-hopset directly corresponds to a distributed distance oracle known as a hub labeling. In this work, we explore centralized distance oracles based on 3-hopsets and display their advantages in several practical scenarios. In particular, for graphs of constant highway dimension, and more generally for graphs of constant skeleton dimension, we show that 3-hopsets require exponentially fewer shortcuts per node than any previously described distance oracle, and also offer a speedup in query time when compared to simple oracles based on a direct application of 2-hopsets. Finally, we consider the problem of computing minimum-size h-hopset (for any h >= 2) for a given graph G, showing a polylogarithmic-factor approximation for the case of unique shortest path graphs. When h=3, for a given bound on the space used by the distance oracle, we provide a construction of hopset achieving polylog approximation both for space and query time compared to the optimal 3-hopset oracle given the space bound.

Siddharth Gupta, Adrian Kosowski, and Laurent Viennot. Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 143:1-143:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ICALP.2019.143, author = {Gupta, Siddharth and Kosowski, Adrian and Viennot, Laurent}, title = {{Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {143:1--143:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.143}, URN = {urn:nbn:de:0030-drops-107199}, doi = {10.4230/LIPIcs.ICALP.2019.143}, annote = {Keywords: Hopsets, Distance Oracles, Graph Algorithms, Data Structures} }

Document

**Published in:** LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

We introduce the problem of hub-laminar decomposition which generalizes that of computing a shortest path with minimum eccentricity (MESP). Intuitively, it consists in decomposing a graph into several paths that collectively have small eccentricity and meet only near their extremities. The problem is related to computing an isometric cycle with minimum eccentricity (MEIC). It is also linked to DNA reconstitution in the context of metagenomics in biology. We show that a graph having such a decomposition with long enough paths can be decomposed in polynomial time with approximated guaranties on the parameters of the decomposition. Moreover, such a decomposition with few paths allows to compute a compact representation of distances with additive distortion. We also show that having an isometric cycle with small eccentricity is related to the possibility of embedding the graph in a cycle with low distortion.

Etienne Birmelé, Fabien de Montgolfier, Léo Planche, and Laurent Viennot. Decomposing a Graph into Shortest Paths with Bounded Eccentricity. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 15:1-15:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{birmele_et_al:LIPIcs.ISAAC.2017.15, author = {Birmel\'{e}, Etienne and de Montgolfier, Fabien and Planche, L\'{e}o and Viennot, Laurent}, title = {{Decomposing a Graph into Shortest Paths with Bounded Eccentricity}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {15:1--15:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.15}, URN = {urn:nbn:de:0030-drops-82621}, doi = {10.4230/LIPIcs.ISAAC.2017.15}, annote = {Keywords: Graph Decomposition, Graph Clustering, Distance Labeling, BFS, MESP} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail