Spanners in sparse graphs

详细信息    查看全文

• 作者：Feodor F. Dragan^a ;   ; ^{dragan@cs.kent.edu} ; Fedor V. Fomin^b ;   ; ¹ ;   ; ^{fedor.fomin@ii.uib.no} ; Petr A. Golovach^c ;   ; ² ;   ; ^{petr.golovach@durham.ac.uk}
• 关键词：Graph algorithms ; Parameterized complexity ; Spanners ; Distances ; Planar graphs ; Apex-minor-free graphs ; Treewidth
• 刊名：Journal of Computer and System Sciences
• 出版年：2011
• 出版时间：November 2011
• 年：2011
• 卷：77
• 期：6
• 页码：1108-1119
• 全文大小：241 K

文摘

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.