Parameterized Complexity of Directed Spanner Problems.

Autor: Fomin FV; Department of Informatics, University of Bergen, PB 7803, 5020 Bergen, Norway., Golovach PA; Department of Informatics, University of Bergen, PB 7803, 5020 Bergen, Norway., Lochet W; Department of Informatics, University of Bergen, PB 7803, 5020 Bergen, Norway., Misra P; Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany., Saurabh S; Department of Informatics, University of Bergen, PB 7803, 5020 Bergen, Norway.; Institute of Mathematical Sciences, HBNI, Chennai, India., Sharma R; Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany.
Jazyk: angličtina
Zdroj: Algorithmica [Algorithmica] 2022; Vol. 84 (8), pp. 2292-2308. Date of Electronic Publication: 2021 Dec 27.
DOI: 10.1007/s00453-021-00911-x
Abstrakt: We initiate the parameterized complexity study of minimum t -spanner problems on directed graphs. For a positive integer t , a multiplicative t -spanner 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 t -spanner 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 t -spanner with at most m - k arcs. Similarly, Directed Additive Spanner asks whether G has an additive t -spanner with at most m - k arcs. We show that (i) Directed Multiplicative Spanner admits a polynomial kernel of size O ( k 4 t 5 ) and can be solved in randomized ( 4 t ) k · n O ( 1 ) time, (ii) the weighted variant of Directed Multiplicative Spanner can be solved in k 2 k · n O ( 1 ) time on directed acyclic graphs, (iii) Directed Additive Spanner is W [ 1 ] -hard when parameterized by k for every fixed t ≥ 1 even when 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 .
(© The Author(s) 2021.)
Databáze: MEDLINE
Externí odkaz: