Search Results

Documents authored by Labourel, Arnaud

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.68
Graph Exploration: The Impact of a Distance Constraint

Authors: Stéphane Devismes, Yoann Dieudonné, and Arnaud Labourel

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
A mobile agent, starting from a node s of a simple undirected connected graph G = (V,E), has to explore all nodes and edges of G using the minimum number of edge traversals. To do so, the agent uses a deterministic algorithm that allows it to gain information on G as it traverses its edges. During its exploration, the agent must always respect the constraint of knowing a path of length at most D to go back to node s. The upper bound D is fixed as being equal to (1+α)r, where r is the eccentricity of node s (i.e., the maximum distance from s to any other node) and α is any positive real constant. This task has been introduced by Duncan et al. [Christian A. Duncan et al., 2006] and is known as distance-constrained exploration. The penalty of an exploration algorithm running in G is the number of edge traversals made by the agent in excess of |E|. In [Petrisor Panaite and Andrzej Pelc, 1999], Panaite and Pelc gave an algorithm for solving exploration without any constraint on the moves that is guaranteed to work in every graph G with a (small) penalty in 𝒪(|V|). Hence, a natural question is whether we can obtain a distance-constrained exploration algorithm with the same guarantee as well. In this paper, we provide a negative answer to this question. We also observe that an algorithm working in every graph G with a linear penalty in |V| cannot be obtained for the task of fuel-constrained exploration, another variant studied in the literature. This solves an open problem posed by Duncan et al. in [Christian A. Duncan et al., 2006] and shows a fundamental separation with the task of exploration without constraint on the moves.
Cite as

Stéphane Devismes, Yoann Dieudonné, and Arnaud Labourel. Graph Exploration: The Impact of a Distance Constraint. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 68:1-68:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{devismes_et_al:LIPIcs.ICALP.2025.68,
  author =	{Devismes, St\'{e}phane and Dieudonn\'{e}, Yoann and Labourel, Arnaud},
  title =	{{Graph Exploration: The Impact of a Distance Constraint}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{68:1--68:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.68},
  URN =		{urn:nbn:de:0030-drops-234452},
  doi =		{10.4230/LIPIcs.ICALP.2025.68},
  annote =	{Keywords: exploration, graph, mobile agent}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.9
Robustness of Distances and Diameter in a Fragile Network

Authors: Arnaud Casteigts, Timothée Corsini, Hervé Hocquard, and Arnaud Labourel

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
A property of a graph G is robust if it remains unchanged in all connected spanning subgraphs of G. This form of robustness is motivated by networking contexts where some links eventually fail permanently, and the network keeps being used so long as it is connected. It is then natural to ask how certain properties of the network may be impacted as the network deteriorates. In this paper, we focus on two particular properties, which are the diameter, and pairwise distances among nodes. Surprisingly, the complexities of deciding whether these properties are robust are quite different: deciding the robustness of the diameter is coNP-complete, whereas deciding the robustness of the distance between two given nodes has a linear time complexity. This is counterintuitive, because the diameter consists of the maximum distance over all pairs of nodes, thus one may expect that the robustness of the diameter reduces to testing the robustness of pairwise distances. On the technical side, the difficulty of the diameter is established through a reduction from hamiltonian paths. The linear time algorithm for deciding robustness of the distance relies on a new characterization of two-terminal series-parallel graphs (TTSPs) in terms of excluded rooted minor, which may be of independent interest.
Cite as

Arnaud Casteigts, Timothée Corsini, Hervé Hocquard, and Arnaud Labourel. Robustness of Distances and Diameter in a Fragile Network. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{casteigts_et_al:LIPIcs.SAND.2022.9,
  author =	{Casteigts, Arnaud and Corsini, Timoth\'{e}e and Hocquard, Herv\'{e} and Labourel, Arnaud},
  title =	{{Robustness of Distances and Diameter in a Fragile Network}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.9},
  URN =		{urn:nbn:de:0030-drops-159514},
  doi =		{10.4230/LIPIcs.SAND.2022.9},
  annote =	{Keywords: Dynamic networks, Longest path, Series-parallel graphs, Rooted minors}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.36
Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs

Authors: Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, and Andrzej Pelc

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh [Baruch Awerbuch et al., 1999] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s. The size of the tank is B = 2(1+α)r, for some positive real constant α, where r, called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most {⌊ B⌋} edge traversals between two consecutive visits at node s. Let e(d) be the number of edges whose at least one extremity is at distance less than d from s. Awerbuch, Betke, Rivest and Singh [Baruch Awerbuch et al., 1999] conjectured that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e(d). We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost 𝒪(e(d) log d), and then show how to modify this algorithm to work in the model from [Baruch Awerbuch et al., 1999] with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost Θ(e(d)) for all graphs and thus our algorithms are also almost optimal.
Cite as

Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, and Andrzej Pelc. Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bouchard_et_al:LIPIcs.ICALP.2021.36,
  author =	{Bouchard, S\'{e}bastien and Dieudonn\'{e}, Yoann and Labourel, Arnaud and Pelc, Andrzej},
  title =	{{Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.36},
  URN =		{urn:nbn:de:0030-drops-141051},
  doi =		{10.4230/LIPIcs.ICALP.2021.36},
  annote =	{Keywords: treasure hunt, graph, mobile agent}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.15
Distance Labeling Schemes for Cube-Free Median Graphs

Authors: Victor Chepoi, Arnaud Labourel, and Sébastien Ratel

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently by merely inspecting the labels of u and v, without using any other information. One of the important problems is finding natural classes of graphs admitting distance labeling schemes with labels of polylogarithmic size. In this paper, we show that the class of cube-free median graphs on n nodes enjoys distance labeling scheme with labels of O(log^3 n) bits.
Cite as

Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance Labeling Schemes for Cube-Free Median Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chepoi_et_al:LIPIcs.MFCS.2019.15,
  author =	{Chepoi, Victor and Labourel, Arnaud and Ratel, S\'{e}bastien},
  title =	{{Distance Labeling Schemes for Cube-Free Median Graphs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.15},
  URN =		{urn:nbn:de:0030-drops-109598},
  doi =		{10.4230/LIPIcs.MFCS.2019.15},
  annote =	{Keywords: median graphs, labeling schemes, distributed distance computation}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact