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.
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:
- 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.
- Solid Grid Graphs: For solid grid graphs (planar grids without "holes"), the authors leverage structural properties related to the graph's boundary.
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