Spanners in Sparse Graphs

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 the

tree t

-spanner problem

(the problem to decide whether

G

admits a tree

t

-spanner) is polynomial time solvable for

t

 ≤ 3 and is NP-complete as long as

t

is part of the input. They also left as an open problem whether the tree

t

-spanner problem is polynomial time solvable for every fixed

t

 ≥ 4. In this work we resolve this open problem and extend the solution in several directions. We show that for every fixed

t

, it is possible in polynomial time not only to decide if a planar graph

G

has a tree

t

-spanner, but also to decide if

G

has a

t

-spanner of

bounded treewidth

. Moreover, for every fixed values of

t

and

k

, the problem, for a given planar graph

G

to decide if

G

has a

t

-spanner of treewidth at most

k

, is not only polynomial time solvable, but is

fixed parameter tractable

(with

k

and

t

being the parameters). In particular, the running time of our algorithm is linear with respect to the size of

G

. We extend this result from planar to a much more general class of sparse graphs containing graphs of bounded genus. An

apex graph

is a graph obtained from a planar graph

G

by adding a vertex and making it adjacent to some vertices of

G

. We show 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

. Graphs of bounded treewidth are sparse graphs and our technique can be used to settle the complexity of the parameterized version of the

sparse t

-spanner problem

, where for given

t

and

m

one asks if a given

n

-vertex graph has a

t

-spanner with at most

n

 − 1 + 

m

edges. Our results imply that the sparse

t

-spanner problem is fixed parameter tractable on apex-minor-free graphs with

t

and

m

being the parameters. Finally we show that the tractability border of the

t

-spanner problem cannot be extended beyond the class of apex-minor-free graphs. In particular, we prove that for every

t

 ≥ 4, the problem of finding a tree

t

-spanner is NP-complete on

K

6

-minor-free graphs

. Thus our results are tight, in a sense that the restriction of input graph being apex-minor-free cannot be replaced by

H

-minor-free for some non-apex fixed graph

H

.