Yusuke Kobayashi (小林 佑輔), An FPT Algorithm for Minimum Additive Spanner Problem

For a positive integer t and a graph G, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus t. Minimum Additive t-Spanner Problem is to find an additive t-spanner with the minimum number of edges in a given graph, which is known to be NP-hard. Since we need to care about global properties of graphs when we deal with additive t-spanners, Minimum Additive t-Spanner Problem is hard to handle, and hence only few results are known for it. In this talk, we study Minimum Additive t-Spanner Problem from the viewpoint of parameterized complexity. We formulate a parameterized version of the problem in which the number of removed edges is regarded as a parameter, and give a fixed-parameter algorithm for it. We also extend our result to (α,β)-spanners.