Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs : A Complete Classification
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2024-07-02
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
19
Series
51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, pp. 1-19, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 297
Abstract
In the Directed Steiner Network problem, the input is a directed graph G, a set T ⊆ V (G) of k terminals, and a demand graph D on T. The task is to find a subgraph H ⊆ G with the minimum number of edges such that for every (s, t) ∈ E(D), the solution H contains a directed s → t path. The goal of this paper is to investigate how the complexity of the problem depends on the demand pattern in planar graphs. Formally, if D is a class of directed graphs, then the D-Steiner Network (D-DSN) problem is the special case where the demand graph D is restricted to be from D. We give a complete characterization of the behavior of every D-DSN problem on planar graphs. We classify every class D closed under transitive equivalence and identification of vertices into three cases: assuming ETH, either the problem is 1. solvable in time 2O(k) · nO(1), i.e., FPT parameterized by the number k of terminals, but not solvable in time 2o(k) · nO(1), 2. solvable in time f(k) · nO(√k), but cannot be solved in time f(k) · no(√k), or 3. solvable in time f(k) · nO(k), but cannot be solved in time f(k) · no(k). Our result is a far-reaching generalization and unification of earlier results on Directed Steiner Tree, Directed Steiner Network, and Strongly Connected Steiner Subgraph on planar graphs. As an important step of our lower bound proof, we discover a rare example of a genuinely planar problem (i.e., described by a planar graph and two sets of vertices) that cannot be solved in time f(k) · no(k): given two sets of terminals S and T with |S| + |T| = k, find a subgraph with minimum number of edges such that every vertex of T is reachable from every vertex of S.Description
Publisher Copyright: © Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, and Roohani Sharma.
Keywords
Directed Steiner Network, Sub-exponential algorithm
Other note
Citation
Galby, E, Kisfaludi-Bak, S, Marx, D & Sharma, R 2024, Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs : A Complete Classification . in K Bringmann, M Grohe, G Puppis & O Svensson (eds), 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024 ., 67, Leibniz International Proceedings in Informatics, LIPIcs, vol. 297, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-19, International Colloquium on Automata, Languages, and Programming, Tallinn, Estonia, 08/07/2024 . https://doi.org/10.4230/LIPIcs.ICALP.2024.67