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/
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
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 |
