论文标题
平面图上的次指数参数化的有向施泰纳网络问题：完整的分类
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
论文作者
论文摘要
在定向的Steiner网络问题中，输入是一个定向的图G，一个称为终端的G顶点的子集T，以及T上的需求图D。任务是找到G的G h g g h g g h g g h g g h g g h g g h g g h g g h g g h g g h g g h g g g g g g g g g g g g g g g g g g g g g g t t t to t to t to t to t to t to t to t path。在本文中，我们研究了问题的复杂性如何取决于G是平面时的需求模式。正式地，如果\ mathcal {d}是在标识的基础下封闭的一类有向图，则\ Mathcal {d} -steiner Network（\ Mathcal {d} -sn）问题是需求图d限制为\ Mathcal {d}的特殊情况。对于一般图，Feldmann和Marx [ICALP 2016]表征了那些需求图的家族，其中问题是固定参数可拖动的（FPT），该终端数k被参数化。他们表明，如果\ Mathcal {d}是五个硬家庭之一的超集，则\ Mathcal {d} -sn为w [1] -HARD由k参数化，否则可以在时间f（k）n^{o（o（1）}中求解。 对于平面图，一个有趣的问题是W [1] hard情况是否可以通过亚指数参数化算法来解决。 Chitnis等。 [SICOMP 2020]表明，假设ETH没有F（k）n^{o（k）}时间算法对于一般\ Mathcal \ Mathcal {d} -sn问题，在平面图上问题，但可以在时间f（k）n^{o（k）n^{o（k）plact plan}中解决的特殊案例，称为steiner stoined stoined stteiner子分类。我们提出了这两个结果的深远概括和统一：我们对平面图上每个$ \ Mathcal {d} $ sn问题的行为进行完整的表征。我们表明，假设问题是（1）在时间2^{o（k）} n^{o（1）}的时间2^{o（k）}，而不是时间2^{o（k）} n^{o（1）}，或（2）在时间f（k）n^{o（k）n^{o（k）n^{o（sqrt）中，但f（k）n^{o（\ sqrt {k}）}或（3）在时间f（k）n^{o（k）}中求解，但不在时间f（k）n^{o（k）n^{o（k）n^{o（k}）}中。
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 \mathcal{D} is a class of directed graphs closed under identification of vertices, then the \mathcal{D}-Steiner Network (\mathcal{D}-SN) problem is the special case where the demand graph D is restricted to be from \mathcal{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 \mathcal{D} is a superset of one of the five hard families, then \mathcal{D}-SN is W[1]-hard parameterized by k, otherwise it can be solved in time f(k)n^{O(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)n^{o(k)} time algorithm for the general \mathcal{D}-SN problem on planar graphs, but the special case called Strongly Connected Steiner Subgraph can be solved in time f(k) n^{O(\sqrt{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 $\mathcal{D}$-SN problem on planar graphs. We show that assuming ETH, either the problem is (1) solvable in time 2^{O(k)}n^{O(1)}, and not in time 2^{o(k)}n^{O(1)}, or (2) solvable in time f(k)n^{O(\sqrt{k})}, but not in time f(k)n^{o(\sqrt{k})}, or (3) solvable in time f(k)n^{O(k)}, but not in time f(k)n^{o({k})}.
