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

DOI10.1137/1.9781611973402.129MaRDI QIDQ5384091zbMATHOpenAlexFDO

Authors Rajesh Chitnis, Dániel Marx, Mohammad T. Hajiaghayi

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.13161

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: (see paper for full abstract) Given a vertex-weighted directed graph $G=(V,E)$ and a set $T=t_1,t_2,ldots{t}_k$ of $k$ terminals, the objective of the SCSS problem is to find a vertex set $HsubseteqV$ of minimum weight such that $G[H]$ contains a $t_{i}ightarrow{t}_j$ path for each $ieqj$. 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)}cdot{n}^{O(sqrtk)}$ algorithm for planar SCSS, which is an improvement of a factor of $O(sqrtk)$ 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)cdot{n}^{o(sqrtk)}$ 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)cdot{n}^{o(k/logk)}$ 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)cdot{n}^{o(k)}$ time algorithm for DSN on acyclic planar graphs.

Recommendations

• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
• A tight algorithm for strongly connected Steiner subgraph on two terminals with demands
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• Parameterized approximation algorithms for bidirected Steiner network problems

Cited in

(11)

• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
• Complexity of the Steiner Network Problem with Respect to the Number of Terminals
• Parameterized approximation algorithms for bidirected Steiner network problems
• A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
• An ETH-tight algorithm for bidirected Steiner connectivity
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• Subexponential parameterized algorithms for graphs of polynomial growth
• A tight algorithm for strongly connected Steiner subgraph on two terminals with demands
• Almost tight lower bounds for hard cutting problems in embedded graphs
• A tight lower bound for planar Steiner orientation

This page was built for publication: Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384091)