NP-completeness results for minimum planar spanners (Q4373672)

The concept of spanner is useful, for example, to synchronize asynchronous networks or to find a sparse subnetwork that nevertheless guarantees constant delay factors. In most applications, the sparseness of a spanner is critical. A \(t\)-spanner of a graph \(G\) is a spanning subgraph \(S\) in which the distance between every pair of vertices is at most \(t\) times their distance in \(G\). A \(t\)-spanner is called a minimum \(t\)-spanner of a weighted graph \(G\) if it has minimum total edge weight among all \(t\)-spanners of \(G\). The problem of finding \(t\)-spanners with a minimum number of edges has been shown to be NP-hard for most values of \(t\) by Cai in 1994. In this paper, the authors restrict the set of input instances. They consider spanners in planar graphs. They define the decision problem Min \( S_t\): given a graph \(G\) with associated edge weights and a positive real value \(W\), does \(G\) contain a \(t\)-spanner with total edge weight at most \(W\)? The authors prove three results: (1) for \(t\geq 5\), Min \(S_t\) is NP-complete for undirected, planar, biconnected graphs with unit edge weights; (2) for \(t\geq 3\), Min \(S_t\) is NP-complete for undirected, planar, biconnected graphs with edge weights equal to 1 or 2; and (3) for \(t\geq 5\) (resp. \(t\geq 3)\), Min \(S_t\) is NP-complete for unweighted (resp. weighted) planar oriented graphs. For the entire collection see [Zbl 0877.00011].