Chakraborty, Dibyayan ;
Das, Sandip ;
Foucaud, Florent ;
Gahlawat, Harmender ;
Lajou, Dimitri ;
Roy, Bodhayan
Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs
Abstract
We study the complexity of finding the geodetic number on subclasses of planar graphs and chordal graphs. A set S of vertices of a graph G is a geodetic set if every vertex of G lies in a shortest path between some pair of vertices of S. The Minimum Geodetic Set (MGS) problem is to find a geodetic set with minimum cardinality of a given graph. The problem is known to remain NPhard on bipartite graphs, chordal graphs, planar graphs and subcubic graphs. We first study MGS on restricted classes of planar graphs: we design a lineartime algorithm for MGS on solid grids, improving on a 3approximation algorithm by Chakraborty et al. (CALDAM, 2020) and show that MGS remains NPhard even for subcubic partial grids of arbitrary girth. This unifies some results in the literature. We then turn our attention to chordal graphs, showing that MGS is fixed parameter tractable for inputs of this class when parameterized by their treewidth (which equals the clique number minus one). This implies a lineartime algorithm for ktrees, for fixed k. Then, we show that MGS is NPhard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012). As interval graphs are very constrained, to prove the latter result we design a rather sophisticated reduction technique to work around their inherent linear structure.
BibTeX  Entry
@InProceedings{chakraborty_et_al:LIPIcs:2020:13351,
author = {Dibyayan Chakraborty and Sandip Das and Florent Foucaud and Harmender Gahlawat and Dimitri Lajou and Bodhayan Roy},
title = {{Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {7:17:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13351},
URN = {urn:nbn:de:0030drops133516},
doi = {10.4230/LIPIcs.ISAAC.2020.7},
annote = {Keywords: Geodetic set, Planar graph, Chordal graph, Interval graph, FPT algorithm}
}
04.12.2020
Keywords: 

Geodetic set, Planar graph, Chordal graph, Interval graph, FPT algorithm 
Seminar: 

31st International Symposium on Algorithms and Computation (ISAAC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 