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

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

Abstract

This paper investigates the computational complexity of the Minimum Geodetic Set (MGS) problem. We demonstrate that MGS is NP-hard for planar graphs with maximum degree six and for line graphs. Furthermore, we establish inapproximability results for graphs with diameter 2, showing that no polynomial-time algorithm can achieve a sublogarithmic approximation factor unless $P=NP$. On the algorithmic side, we present an $O(\sqrt[3]{n}\log n)$-approximation for general graphs and a constant-factor 3-approximation for solid grid graphs.

Introduction

In graph theory, a set of vertices $S$ is a geodetic set if every vertex of the graph lies on at least one shortest path between some pair of vertices in $S$. The Minimum Geodetic Set (MGS) problem asks for the smallest such set. This problem is fundamental to network analysis, representing the minimum number of "anchors" needed to cover a network via shortest-path routing.

Complexity and Hardness

While MGS is known to be NP-hard for general graphs, this research extends these boundaries to more structured graph classes. The authors prove that the problem remains NP-hard for planar graphs with a maximum degree of six and for line graphs. These proofs involve transforming known difficult problems, such as the Minimum Dominating Set on subcubic planar graphs, into the MGS problem using intricate gadget-based reductions.

Complexity reduction gadget for NP-hardness proofs.

Additionally, the paper reveals that structural simplicity does not always imply computational ease. Even in graphs with a diameter of 2—where any two nodes are at most two steps apart—finding an optimal geodetic set remains hard to approximate within a logarithmic factor.

Approximation Algorithms

Given the hardness results, the paper focuses on developing approximation algorithms with provable performance guarantees:

  1. General Graphs: By establishing a reduction to the Minimum Rainbow Subgraph of Multigraph (MRSM) problem, the authors provide an $O(\sqrt[3]{n} \log n)$-approximation. This is the first sublinear approximation algorithm for MGS on general graphs.
  2. Solid Grid Graphs: For solid grid graphs (planar grids without "holes"), the authors leverage structural properties related to the graph's boundary.
Structural analysis of solid grid graphs.

The study identifies "corner vertices"—nodes with low degree on the boundary—as essential components. It is proven that the set of all corner vertices forms a geodetic set whose size is at most three times that of the optimal set, yielding a practical 3-approximation algorithm.

Conclusion and Future Work

This work clarifies the complexity of the MGS problem across several important graph families. While providing a significant step forward with the first sublinear approximation for general graphs and a tight constant-factor approximation for grid graphs, a gap remains between the logarithmic hardness lower bound and the current algorithmic upper bounds. Future research may focus on closing this gap or finding constant-factor approximations for planar and line graphs.

Summary updated

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 \textsc{Minimum Geodetic Set (MGS)} problem is to find a geodetic set with minimum cardinality. In this paper, we prove that solving the \textsc{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 \textsc{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 $O\left(\sqrt[3]{n}\log n\right)$-approximation algorithm for the \textsc{MGS} problem on general graphs of order $n$. We also give a $3$-approximation algorithm for the \textsc{MGS} problem on the family of solid grid graphs which is a subclass of planar graphs.
BibTeX
@inproceedings{chakraborty2019hardness,
  author = {Dibyayan Chakraborty and Florent Foucaud and Harmender Gahlawat and Subir Kumar Ghosh and Bodhayan Roy},
  title = {{Hardness and approximation for the geodetic set problem in some graph classes}},
  booktitle = {CALDAM},
  year = {2019},
  doi = {10.1007/978-3-030-39219-2\_9},
}
Figure