On January 20, 2021, Yusuke Kobayashi (小林 佑輔) from RIMS, Kyoto University gave an online talk at the Virtual Discrete Math Colloquium on the fixed-parameter tractability of the problem of finding a small set X of edges such that for every pair v, w of vertices the distance from v to w in G is at most a constant plus the distance from v to w in G-X. The title of his talk was “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.
