Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
share
(see paper for full abstract) Given a vertex-weighted directed graph G=(V,E) and a set T={t_1, t_2, ... t_k} of k terminals, the objective of the SCSS problem is to find a vertex set H⊆ V of minimum weight such that G[H] contains a t_i→ t_j path for each i≠ j. The problem is NP-hard, but Feldman and Ruhl [FOCS '99; SICOMP '06] gave a novel n^O(k) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs: - Our main algorithmic result is a 2^O(k)· n^O(√(k)) algorithm for planar SCSS, which is an improvement of a factor of O(√(k)) in the exponent over the algorithm of Feldman and Ruhl. - Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an f(k)· n^o(√(k)) algorithm for any computable function f, unless the Exponential Time Hypothesis (ETH) fails. The following additional results put our upper and lower bounds in context: - In general graphs, we cannot hope for such a dramatic improvement over the n^O(k) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an f(k)· n^o(k/log k) algorithm for any computable function f. - Feldman and Ruhl generalized their n^O(k) algorithm to the more general Directed Steiner Network (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source s_i there is a path to the corresponding terminal t_i. We show that, assuming ETH, there is no f(k)· n^o(k) time algorithm for DSN on acyclic planar graphs.
READ FULL TEXT