License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.40
URN: urn:nbn:de:0030-drops-173251
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17325/
Go to the corresponding LIPIcs Volume Portal

Dumas, Maël ; Foucaud, Florent ; Perez, Anthony ; Todinca, Ioan

On Graphs Coverable by k Shortest Paths

pdf-format:
LIPIcs-ISAAC-2022-40.pdf (0.9 MB)

Abstract

We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a function of k. As a corollary, we prove that the problem Isometric Path Cover with Terminals (which, given a graph G and a set of k pairs of vertices called terminals, asks whether G can be covered by k shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem Strong Geodetic Set with Terminals (which, given a graph G and a set of k terminals, asks whether there exist binom(k,2) shortest paths, each joining a distinct pair of terminals such that these paths cover G). Moreover, this implies that the related problems Isometric Path Cover and Strong Geodetic Set (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter k.

BibTeX - Entry

@InProceedings{dumas_et_al:LIPIcs.ISAAC.2022.40,
  author =	{Dumas, Ma\"{e}l and Foucaud, Florent and Perez, Anthony and Todinca, Ioan},
  title =	{{On Graphs Coverable by k Shortest Paths}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17325},
  URN =		{urn:nbn:de:0030-drops-173251},
  doi =		{10.4230/LIPIcs.ISAAC.2022.40},
  annote =	{Keywords: Shortest paths, covering problems, parameterized complexity}
}

Keywords: Shortest paths, covering problems, parameterized complexity
Collection: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI