Vis enkel innførsel

dc.contributor.authorFomin, Fedor
dc.contributor.authorGolovach, Petr
dc.contributor.authorLochet, William
dc.contributor.authorMisra, Pranabendu
dc.contributor.authorSaurabh, Saket
dc.contributor.authorSharma, Roohani
dc.PublishedLeibniz International Proceedings in Informatics. 2020, 180 12:1-12:11.
dc.description.abstractWe 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 - 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.en_US
dc.publisherDagstuhl Publishingen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.rightsNavngivelse 4.0 Internasjonal*
dc.titleParameterized Complexity of Directed Spanner Problemsen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.rights.holderCopyright 2020 The Authorsen_US
dc.source.journalLeibniz International Proceedings in Informaticsen_US
dc.relation.projectNorges forskningsråd: 263317en_US
dc.identifier.citationLeibniz International Proceedings in Informatics. 2020, 180, 12:1-12:11en_US

Tilhørende fil(er)


Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Navngivelse 4.0 Internasjonal
Med mindre annet er angitt, så er denne innførselen lisensiert som Navngivelse 4.0 Internasjonal