Search Results

Documents authored by Beaudou, Laurent

Document
DOI: 10.4230/LIPIcs.MFCS.2026.88
Structural Parameterizations of Geodetic Set on Directed (Acyclic) Graphs

Authors: Laurent Beaudou, Florent Foucaud, Lucas Lorieau, and Prafullkumar Tale

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
In Directed Geodetic Set, we are given a (directed) graph and seek a small solution set S ⊆ V(G) such that every vertex lies on a shortest directed path between two vertices in S. While most prior work on Directed Geodetic Set has focused on undirected graphs, in this article we study the problem on directed graphs from the perspective of parameterized complexity. It is known that the problem is W[2]-hard when parameterized by the solution size k, even on directed acyclic graphs (DAGs). We investigate structural parameterizations of the problem. Our first result is a kernel of size 2^O(vcn) for Directed Geodetic Set on general digraphs, where vcn denotes the vertex cover number of the underlying (undirected) graph. This implies an algorithm running in time 2^O(vcn²) ⋅ n^O(1). Furthermore, we prove that, assuming the ETH, the problem does not admit an algorithm running in time 2^o(vcn²) ⋅ n^O(1). Such a tight quadratic exponential lower bound in the parameter is relatively uncommon in parameterized complexity. These results generalize earlier work on undirected graphs by Foucaud et al. [STACS 2025], and complements a recent result on directed graph by Foucaud et al. [CALDAM 2026], that showed that the problem is para-NP-hard for the pathwidth and feedback vertex set number of the underlying graph. Next, we show that on general digraphs, Directed Geodetic Set admits a natural kernel of size (kΔ)^O(rdiam), where Δ is the maximum degree and rdiam denotes the reachability diameter of the digraph (a natural analogue of diameter of undirected graphs). This yields an algorithm running in time (kΔ)^O(rdiam⋅k) ⋅ n^O(1). We further prove that, assuming the ETH, the problem does not admit an algorithm running in time (kΔ)^o(rdiam ⋅ k) ⋅ n^O(1). Finally, we justify the necessity of combining parameters by establishing the following hardness results for Directed Geodetic Set: 1) It is W[2]-hard parameterized by k, even on digraphs of maximum degree 3. 2) It is para-NP-hard parameterized by maximum degree and reachability diameter. One can infer that the problem remains W[2]-hard when parameterized by k, even on graphs of reachability diameter 3 from Araújo and Arraes [DAM 2022]. All our conditional lower bounds and hardness results hold even when the input digraph is restricted to be a DAG.
Cite as

Laurent Beaudou, Florent Foucaud, Lucas Lorieau, and Prafullkumar Tale. Structural Parameterizations of Geodetic Set on Directed (Acyclic) Graphs. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 88:1-88:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{beaudou_et_al:LIPIcs.MFCS.2026.88,
  author =	{Beaudou, Laurent and Foucaud, Florent and Lorieau, Lucas and Tale, Prafullkumar},
  title =	{{Structural Parameterizations of Geodetic Set on Directed (Acyclic) Graphs}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{88:1--88:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.88},
  URN =		{urn:nbn:de:0030-drops-274708},
  doi =		{10.4230/LIPIcs.MFCS.2026.88},
  annote =	{Keywords: Geodetic Set, Directed Graphs, NP-hardness, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.19
The Canadian Traveller Problem on Outerplanar Graphs

Authors: Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev, Antoine Dailly, Yan Gerard, Aurélie Lagoutte, Vincent Limouzy, and Lucas Pastor

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
We study the k-Canadian Traveller Problem, where a weighted graph G = (V,E,ω) with a source s ∈ V and a target t ∈ V are given. This problem also has a hidden input E_* ⊊ E of cardinality at most k representing blocked edges. The objective is to travel from s to t with the minimum distance. At the beginning of the walk, the blockages E_* are unknown: the traveller discovers that an edge is blocked when visiting one of its endpoints. Online algorithms, also called strategies, have been proposed for this problem and assessed with the competitive ratio, i.e., the ratio between the distance actually traversed by the traveller divided by the distance he would have traversed knowing the blockages in advance. Even though the optimal competitive ratio is 2k+1 even on unit-weighted planar graphs of treewidth 2, we design a polynomial-time strategy achieving competitive ratio 9 on unit-weighted outerplanar graphs. This value 9 also stands as a lower bound for this family of graphs as we prove that, for any ε > 0, no strategy can achieve a competitive ratio 9-ε. Finally, we show that it is not possible to achieve a constant competitive ratio (independent of G and k) on weighted outerplanar graphs.
Cite as

Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev, Antoine Dailly, Yan Gerard, Aurélie Lagoutte, Vincent Limouzy, and Lucas Pastor. The Canadian Traveller Problem on Outerplanar Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{beaudou_et_al:LIPIcs.MFCS.2024.19,
  author =	{Beaudou, Laurent and Berg\'{e}, Pierre and Chernyshev, Vsevolod and Dailly, Antoine and Gerard, Yan and Lagoutte, Aur\'{e}lie and Limouzy, Vincent and Pastor, Lucas},
  title =	{{The Canadian Traveller Problem on Outerplanar Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.19},
  URN =		{urn:nbn:de:0030-drops-205750},
  doi =		{10.4230/LIPIcs.MFCS.2024.19},
  annote =	{Keywords: Canadian Traveller Problem, Online algorithms, Competitive analysis, Outerplanar graphs}
}

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact