NP-hardness and fixed-parameter tractability of the minimum spanner problem

For a positive integer t, a t-spanner of a graph G is a spanning subgraph in which the distance between every pair of vertices is at most t times of their distance in G. In this paper, we consider the problem of finding a t-spanner with minimum number of edges in a given graph, which we call Minimum t -Spanner Problem. For t ≥ 2, Minimum t -Spanner Problem is known to be NP-hard in general graphs. When the input graph is planar, it is shown by Brandes and Handke in 1997 that this problem is NP-hard for t ≥ 5. Since then, the case of t ∈ { 2, 3, 4 } has been open for more than two decades. The main contribution of this paper is to settle this open problem by showing the NP-hardness of Minimum t -Spanner Problem in planar graphs for t ∈ { 2, 3, 4 }. As a byproduct, we show the NP-hardness of the problem on degree-bounded graphs, which improves previously known degree-bounds. We also present a fixed-parameter algorithm for this problem in which the number of removed edges is regarded as a parameter.

Authors

• Yusuke Kobayashi Kyoto University

Keywords

• Minimum Spanner Problem
• Planar graphs
• Degree-bounded graphs
• NP-hardness
• FPT algorithm