- No file added yet -

# Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification

conference contribution

posted on 2024-07-25, 12:39 authored by Esther Galby, Sándor Kisfaludi-Bak, Dániel MarxDániel Marx, Roohani SharmaIn 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 𝒟 is a class of directed graphs, then the 𝒟-Steiner Network (𝒟-DSN) problem is the special case where the demand graph D is restricted to be from 𝒟. We give a complete characterization of the behavior of every 𝒟-DSN problem on planar graphs. We classify every class 𝒟 closed under transitive equivalence and identification of vertices into three cases: assuming ETH, either the problem is 1) solvable in time 2^O(k)⋅n^O(1), i.e., FPT parameterized by the number k of terminals, but not solvable in time 2^o(k)⋅n^O(1), 2) solvable in time f(k)⋅n^O(√k), but cannot be solved in time f(k)⋅n^o(√k), or 3) solvable in time f(k)⋅n^O(k), but cannot be solved in time f(k)⋅n^o(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)⋅n^o(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.

## History

## Editor

Bringmann K ; Grohe M ; Puppis G ; Svensson O## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

International Colloquium on Automata Languages and Programming (ICALP)## Journal

51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)## Volume

297## Page Range

67:1-67:19## Publisher

Schloss Dagstuhl – Leibniz-Zentrum für Informatik## BibTeX

@inproceedings{Galby:Kisfaludi-Bak:Marx:Sharma:2024, title = "Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification", author = "Galby, Esther" AND "Kisfaludi-Bak, Sándor" AND "Marx, Dániel" AND "Sharma, Roohani", editor = "Bringmann, Karl" AND "Grohe, Martin" AND "Puppis, Gabriele" AND "Svensson, Ola", year = 2024, month = 7, journal = "51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)", pages = "67:1--67:19", publisher = "Schloss Dagstuhl – Leibniz-Zentrum für Informatik", issn = "1868-8969", doi = "10.4230/LIPIcs.ICALP.2024.67" }## Usage metrics

## Categories

No categories selected## Keywords

## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC