| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
On Directed Steiner Trees with Multiple Roots | Ondřej Suchý
; | Date: |
18 Apr 2016 | 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 $q
ge 2$. Then we restrict ourselves to instances with $R subseteq T$.
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(q log q+|T|log
q)}cdot n^{O(sqrt{q})})$ time. | Source: | arXiv, 1604.5103 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |