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. If
S is required to be a
tree then
S is called a
tree t-spanner of
G. In 1998, Fekete and Kremer showed that on unweighted planar graphs deciding whether
G admits a
tree t-
spanner is polynomial time solvable for and is NP-complete when
t is part of the input. They also left as an open problem if the problem is polynomial time solvable for every fixed . In this work we resolve the open question of Fekete and Kremer by proving much more general results:
?#xA0; | The problem of finding a t-spanner of treewidth at most k in a given planar graph G is fixed parameter tractable parameterized by k and t. Moreover, for every fixed t and k, the running time of our algorithm is linear.
|
?#xA0; | Our technique allows to extend the result from planar graphs to much more general classes of graphs. An apex graph is a graph that can be made planar by the removal of a single vertex. We prove that the problem of finding a t-spanner of treewidth k is fixed parameter tractable on graphs that do not contain some fixed apex graph as a minor, i.e. on apex-minor-free graphs. The class of apex-minor-free graphs contains planar graphs and graphs of bounded genus.
|
?#xA0; | Finally, we show that the tractability border of the t-spanner problem cannot be extended beyond the class of apex-minor-free graphs and in this sense our results are tight. In particular, for every , the problem of finding a tree t-spanner is NP-complete on -minor-free graphs.
|