On directed Steiner trees with multiple roots

DOI10.1007/978-3-662-53536-3_22MaRDI QIDQ3181063zbMATH OpenOpenAlexFDO

Authors Ondřej Suchý

Publication date 22 December 2016

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: We introduce a new Steiner-type problem for directed graphs named extsc{$q$-Root Steiner Tree}. Here one is given a directed graph $G=(V,A)$ and two subsets of its vertices, $R$ of size $q$ and $T$, and the task is to find a minimum size subgraph of $G$ that contains a path from each vertex of $R$ to each vertex of $T$. The special case of this problem with $q=1$ is the well known extsc{Directed Steiner Tree} problem, while the special case with $T=R$ is the extsc{Strongly Connected Steiner Subgraph} problem. We first show that the problem is W[1]-hard with respect to $|T|$ for any $qge2$. Then we restrict ourselves to instances with $RsubseteqT$. Generalizing the methods of Feldman and Ruhl [SIAM J. Comput. 2006], we present an algorithm for this restriction with running time $O(2^{2q+4|T|}cdot{n}^{2q+O(1)})$, i.e., this restriction is FPT with respect to $|T|$ for any constant $q$. We further show that we can, without significantly affecting the achievable running time, loosen the restriction to only requiring that in the solution there are a vertex $v$ and a path from each vertex of $R$ to $v$ and from $v$ to each vertex of~$T$. Finally, we use the methods of Chitnis et al. [SODA 2014] to show that the restricted version can be solved in planar graphs in $O(2^{O(qlogq+|T|logq)}cdot{n}^{O(sqrtq)})$ time.

Recommendations

• Directed Steiner problems with connectivity constraints
• scientific article; zbMATH DE number 2119644
• Multi-rooted greedy approximation of directed Steiner trees with applications
• Multi-rooted greedy approximation of directed Steiner trees with applications
• Directed Steiner tree with branching constraint

Cites work

• Approximating node connectivity problems via set covers
• Approximation Algorithms for Directed Steiner Problems
• Approximation algorithms for spanner problems and directed Steiner forest
• Can you beat treewidth?
• Dynamic programming for minimum Steiner trees
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Fixed-Parameter and Approximation Algorithms: A New Look
• Fourier meets M\"{o}bius: fast subset convolution
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3384060 (Why is no real title available?)
• Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
• On directed Steiner trees with multiple roots
• On the complexity of k-SAT
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Parameterized algorithms
• Parameterized complexity of arc-weighted directed Steiner problems
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Steiner's problem in graphs and its implications
• The complexity landscape of fixed-parameter directed Steiner network problems
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• The Rectilinear Steiner Tree Problem is NP-Complete
• The steiner problem in graphs

Cited in

(5)

• Clearing directed subgraphs by mobile agents. Variations on covering with paths
• On directed Steiner trees with multiple roots
• Multi-Level Steiner Trees.
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• The complexity landscape of fixed-parameter directed Steiner network problems

This page was built for publication: On directed Steiner trees with multiple roots

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