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

DOI10.1137/1.9781611973402.129zbMATH Open1421.68112arXiv1911.13161OpenAlexW2989902795MaRDI QIDQ5384091FDOQ5384091

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)

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.

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

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

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)

Cited In (11)

• Title not available (Why is that?)
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• An ETH-tight algorithm for bidirected Steiner connectivity
• Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
• Complexity of the Steiner Network Problem with Respect to the Number of Terminals
• Subexponential parameterized algorithms for graphs of polynomial growth
• A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
• A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
• A tight lower bound for planar Steiner orientation
• A tight algorithm for strongly connected Steiner subgraph on two terminals with demands

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)