2022/08/11 by Galby, Esther, Kisfaludi-Bak, Sandor, Marx, Daniel +1
#68Q25 #68Q27 #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2208.06015
In the Directed Steiner Network problem, the input is a directed graph G, a subset T of k vertices of G called the terminals, and a demand graph D on T. The task is to find a subgraph H of G with the minimum number of edges such that for every edge (s,t) in D, the solution H contains a directed s to t path. In this paper we investigate how the complexity of the problem depends on the demand pattern when G is planar. Formally, if D is a class of directed graphs closed under identification of vertices, then the D-Steiner Network (D-SN) problem is the special case where the demand graph D is restricted to be from D. For general graphs, Feldmann and Marx [ICALP 2016] characterized those families of demand graphs where the problem is fixed-parameter tractable (FPT) parameterized by the number k of terminals. They showed that if D is a superset of one of the five hard families, then D-SN is W[1]-hard parameterized by k, otherwise it can be solved in time f(k)nO(1). For planar graphs an interesting question is whether the W[1]-hard cases can be solved by subexponential parameterized algorithms. Chitnis et al. [SICOMP 2020] showed that, assuming the ETH, there is no f(k)no(k) time algorithm for the general D-SN problem on planar graphs, but the special case called Strongly Connected Steiner Subgraph can be solved in time f(k) nO(√(k)) on planar graphs. We present a far-reaching generalization and unification of these two results: we give a complete characterization of the behavior of every D-SN problem on planar graphs. We show that assuming ETH, either the problem is (1) solvable in time 2O(k)nO(1), and not in time 2o(k)nO(1), or (2) solvable in time f(k)nO(√(k)), but not in time f(k)no(√(k)), or (3) solvable in time f(k)nO(k), but not in time f(k)n^o(k).