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

DOI10.1007/978-3-030-39219-2_9zbMATH Open1453.68127arXiv1909.08795OpenAlexW2974470551MaRDI QIDQ779181FDOQ779181

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

Publication date: 21 July 2020

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.

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

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

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)

Cited In (13)

• Computational Complexity of Geodetic Set
• On pitfalls in computing the geodetic number of a graph
• Well-partitioned chordal graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Algorithms and complexity for geodetic sets on partial grids
• Three problems on well-partitioned chordal graphs
• STRONG k-GEODETIC PROBLEM IN GRAPHS: COMPUTATIONAL COMPLEXITY AND SOME RESULTS
• Title not available (Why is that?)
• On the approximation hardness of geodetic set and its variants
• Parameterized Complexity of Geodetic Set
• Parameterized Complexity of Geodetic Set
• On the hardness of finding the geodetic number of a subcubic graph
• Title not available (Why is that?)

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)