NP-COMPLETENESS OF MINIMUM SPANNER PROBLEMS

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. This notion is motivated by applications in distributed systems, communication networks, computational geometry and robotics. In this paper, it is shown that for any fixed t greater-than-or-equal-to 2, the problem of determining, for a graph G and a positive integer K, whether G contains a t-spanner with at most K edges is NP-complete, even if G is a bipartite graph (for fixed t greater-than-or-equal-to 3). The problem for digraphs is also shown to be NP-complete, even for oriented graphs (with fixed t greater-than-or-equal-to 3).