Fomin, Fedor V. ;
Golovach, Petr A. ;
Lochet, William ;
Misra, Pranabendu ;
Saurabh, Saket ;
Sharma, Roohani
Parameterized Complexity of Directed Spanner Problems
Abstract
We initiate the parameterized complexity study of minimum tspanner problems on directed graphs. For a positive integer t, a multiplicative tspanner of a (directed) graph G is a spanning subgraph H such that the distance between any two vertices in H is at most t times the distance between these vertices in G, that is, H keeps the distances in G up to the distortion (or stretch) factor t. An additive tspanner is defined as a spanning subgraph that keeps the distances up to the additive distortion parameter t, that is, the distances in H and G differ by at most t. The task of Directed Multiplicative Spanner is, given a directed graph G with m arcs and positive integers t and k, decide whether G has a multiplicative tspanner with at most mk arcs. Similarly, Directed Additive Spanner asks whether G has an additive tspanner with at most mk arcs. We show that
 Directed Multiplicative Spanner admits a polynomial kernel of size 𝒪(k⁴t⁵) and can be solved in randomized (4t)^k⋅ n^𝒪(1) time,
 Directed Additive Spanner is W[1]hard when parameterized by k even if t = 1 and the input graphs are restricted to be directed acyclic graphs. The latter claim contrasts with the recent result of Kobayashi from STACS 2020 that the problem for undirected graphs is FPT when parameterized by t and k.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs:2020:13315,
author = {Fedor V. Fomin and Petr A. Golovach and William Lochet and Pranabendu Misra and Saket Saurabh and Roohani Sharma},
title = {{Parameterized Complexity of Directed Spanner Problems}},
booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
pages = {12:112:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771726},
ISSN = {18688969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13315},
URN = {urn:nbn:de:0030drops133156},
doi = {10.4230/LIPIcs.IPEC.2020.12},
annote = {Keywords: Graph spanners, directed graphs, parameterized complexity, kernelization}
}
04.12.2020
Keywords: 

Graph spanners, directed graphs, parameterized complexity, kernelization 
Seminar: 

15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 