Hardness and approximation for the geodetic set problem in some graph classes

DOI10.1007/978-3-030-39219-2_9MaRDI QIDQ779181zbMATH OpenOpenAlexFDO

Authors Dibyayan Chakraborty, Florent Foucaud, Harmender Gahlawat, Bodhayan Roy, Subir Kumar Ghosh

Publication date 21 July 2020

Full work available at URL https://arxiv.org/abs/1909.08795

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Abstract: In this paper, we study the computational complexity of finding the emph{geodetic number} of graphs. A set of vertices $S$ of a graph $G$ is a emph{geodetic set} if any vertex of $G$ lies in some shortest path between some pair of vertices from $S$. The extsc{Minimum Geodetic Set (MGS)} problem is to find a geodetic set with minimum cardinality. In this paper, we prove that solving the extsc{MGS} problem is NP-hard on planar graphs with a maximum degree six and line graphs. We also show that unless $P=NP$, there is no polynomial time algorithm to solve the extsc{MGS} problem with sublogarithmic approximation factor (in terms of the number of vertices) even on graphs with diameter $2$. On the positive side, we give an $Oleft(sqrt[3]nlognight)$-approximation algorithm for the extsc{MGS} problem on general graphs of order $n$. We also give a $3$-approximation algorithm for the extsc{MGS} problem on the family of solid grid graphs which is a subclass of planar graphs.

Recommendations

• On the hardness of finding the geodetic number of a subcubic graph
• Parameterized complexity of geodetic set
• Some remarks on the geodetic number of a graph
• Computational Complexity of Geodetic Set
• On the geodetic and geodetic domination numbers of a graph

Cited in

(18)

• Algorithms and complexity for geodetic sets on partial grids
• Well-partitioned chordal graphs
• Computational Complexity of Geodetic Set
• scientific article; zbMATH DE number 2081090 (Why is no real title available?)
• On the computational complexity of the strong geodetic recognition problem
• Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs
• Computing minimum geodetic sets of proper interval graphs
• Parameterized complexity of geodetic set
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Three problems on well-partitioned chordal graphs
• STRONG k-GEODETIC PROBLEM IN GRAPHS: COMPUTATIONAL COMPLEXITY AND SOME RESULTS
• On the hardness of finding the geodetic number of a subcubic graph
• Parameterized Complexity of Geodetic Set
• Algorithmic upper bounds for graph geodetic number
• Symbolic regression for approximating graph geodetic number
• On pitfalls in computing the geodetic number of a graph
• On the approximation hardness of geodetic set and its variants
• scientific article; zbMATH DE number 7765365 (Why is no real title available?)

This page was built for publication: Hardness and approximation for the geodetic set problem in some graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q779181)