Tight bounds for planar strongly connected steiner subgraph with fixed number of terminals (and extensions)

Rajesh Chitnis, Mohammadtaghi Hajiaghayi, Dániel Marx

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Citations (Scopus)

Abstract

Given a vertex-weighted directed graph G = (V,E) and a set T = {t 1 ,t2,...,tk} of k terminals, the objective of the Strongly Connected Steiner Subgraph (SCSS) problem is to find a vertex set H ⊆ V of minimum weight such that G[H] contains a ti →; tj path for each i ≠ j. The problem is NP-hard, but Feldman and Ruhl (FOCS '99; SICOMP '06) gave a novel nO(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 log 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) · no(√k) algorithm for any com-putable function /, unless the Exponential Time Hypothesis (ETH) fails. The algorithm eventually relies on the excluded grid theorem for planar graphs, but we stress that it is not simply a straightforward application of treewidth-based techniques: we need several layers of abstraction to arrive to a problem formulation where the speedup due to planarity can be exploited. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a grid-like fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: Our 2O(k log k) · n o(√k) algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. In general graphs, we cannot hope for such a dramatic improvement over the nO(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 /. Feldman and Ruhl generalized their nO(k) algorithm to the more general Directed Steiner Forest (DSF) problem; here the task is to find a subgraph of minimum weight such that for every source si, there is a path to the corresponding terminal ti.We show that that, assuming ETH, there is no f(k) · no(k)time algorithm for DSF on acyclic planar graphs.

Original languageEnglish
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
EditorsChandra Chekuri
PublisherAssociation for Computing Machinery
Pages1782-1801
ISBN (Electronic)9781611973402
ISBN (Print)9781611973389
Publication statusPublished - 5 Jan 2014
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
Duration: 5 Jan 20147 Jan 2014

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Country/TerritoryUnited States
CityPortland, OR
Period5/01/147/01/14

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Tight bounds for planar strongly connected steiner subgraph with fixed number of terminals (and extensions)'. Together they form a unique fingerprint.

Cite this