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.12
URN: urn:nbn:de:0030-drops-172974
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17297/
Go to the corresponding LIPIcs Volume Portal


Chakraborty, Dibyayan ; Dailly, Antoine ; Das, Sandip ; Foucaud, Florent ; Gahlawat, Harmender ; Ghosh, Subir Kumar

Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond

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


Abstract

A path is isometric if it is a shortest path between its endpoints. In this article, we consider the graph covering problem Isometric Path Cover, where we want to cover all the vertices of the graph using a minimum-size set of isometric paths. Although this problem has been considered from a structural point of view (in particular, regarding applications to pursuit-evasion games), it is little studied from the algorithmic perspective. We consider Isometric Path Cover on chordal graphs, and show that the problem is NP-hard for this class. On the positive side, for chordal graphs, we design a 4-approximation algorithm and an FPT algorithm for the parameter solution size. The approximation algorithm is based on a reduction to the classic path covering problem on a suitable directed acyclic graph obtained from a breadth first search traversal of the graph. The approximation ratio of our algorithm is 3 for interval graphs and 2 for proper interval graphs. Moreover, we extend the analysis of our approximation algorithm to k-chordal graphs (graphs whose induced cycles have length at most k) by showing that it has an approximation ratio of k+7 for such graphs, and to graphs of treelength at most ?, where the approximation ratio is at most 6?+2.

BibTeX - Entry

@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2022.12,
  author =	{Chakraborty, Dibyayan and Dailly, Antoine and Das, Sandip and Foucaud, Florent and Gahlawat, Harmender and Ghosh, Subir Kumar},
  title =	{{Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{12:1--12:17},
  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/17297},
  URN =		{urn:nbn:de:0030-drops-172974},
  doi =		{10.4230/LIPIcs.ISAAC.2022.12},
  annote =	{Keywords: Shortest paths, Isometric path cover, Chordal graph, Interval graph, AT-free graph, Approximation algorithm, FPT algorithm, Treewidth, Chordality, Treelength}
}

Keywords: Shortest paths, Isometric path cover, Chordal graph, Interval graph, AT-free graph, Approximation algorithm, FPT algorithm, Treewidth, Chordality, Treelength
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