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

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

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

(23)

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

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)