arXiv:1604.05103v1 [] 18 Apr 2016

On Directed Steiner Trees with Multiple Roots
Ondřej Suchý
Department of Theoretical Computer Science,
Faculty of Information Technology,
Czech Technical University in Prague, Prague, Czech Republic
ondrej.suchy@fit.cvut.cz
February 27, 2018
Abstract
We introduce a new Steiner-type problem for directed graphs named
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 Directed Steiner Tree problem, while the special case
with T = R is the Strongly Connected Steiner Subgraph problem.
We first show that the problem is W[1]-hard with respect to |T | for any
q ≥ 2. Then we restrict ourselves to instances with R ⊆ T . Generalizing
the methods of Feldman and Ruhl [SIAM J. Comput. 2006], we present
an algorithm for this restriction with running time O(22q+4|T | · n2q+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(2O(q log q+|T | log q) ·
O( q)
) time.
n

1

Introduction

Steiner type problems are one of the most fundamental problems in the network
design. In general words the task is to connect a given set of points at the minimum cost. The study of these problems in graphs was initiated independently
by Hakimi [18] and Levin [25]. In the classic Steiner Tree one is given a
(weighted) undirected graph G = (V, E) and a set T of its vertices (terminals)
and the task is to find a minimum cost connected subgraph containing all the
terminals.

1

In directed graphs, the notion of connectivity is more complicated. The
notion which turns out to be the closest to the undirected Steiner Tree is
that of Directed Steiner Tree (DST), where one is given a (weighted)
directed graph G = (V, A), a set T of terminals, and additionally a root vertex
r and the task is to find a minimum weight subgraph that provides a path
from r to each of T . Another natural option is, given a digraph G = (V, A)
and a set T of terminals, to search for a minimum cost subgraph that provides
a path between each pair of terminals in both directions. This is problem is
called Strongly Connected Steiner Subgraph (SCSS). The most general
problem allows to prescribe the demanded connection between the terminals.
Namely, in Directed Steiner Network (DSN) one is given a digraph G =
(V, A) and a set of q pairs of vertices {(s1 , t1 ), . . . , (sq , tq )} and is asked to find
a minimum weight subgraph H of G that contains a directed path from si to ti
for every i.
Obviously, DSN is a generalization of both DST and SCSS. In this paper
we consider a special case of DSN, which is still a very natural generalization of
both DST and SCSS, namely the following problem:
q-Root Steiner Tree (q-RST)
Input: A directed graph G = (V, A), two subsets of its vertices R, T ⊆ V
with |R| = q, and a positive integer k.
Question: Is there a set S ⊆ V of size at most k such that in G[R ∪ S ∪ T ]
there is a directed path from r to t for every r ∈ R and every t ∈ T ?
If q = 1, then q-RST problem is equal to (unweighted) DST. On the other
hand, if we let T = R, then the problem is equivalent to (unweighted) SCSS
on the terminal set T . We study the problem from a multivariate perspective,
examining the influence of various parameters on the complexity of the problem.
We focus on the following parameters: number of roots q = |R|, number of
terminals |T |, and to a limited extent also to the budget k. Thorough the paper
we denote n = |V | and m = |A|. Before we present our results, let us summarize
what is known about the problems.
Known Results Steiner Tree is NP-hard [16] and remains so even in very
restricted planar cases [15]. As the NP-hardness can be easily transferred also
to DST and SCSS, the problems were studied from approximation perspective.
However, in general terms, the problems are also hard to approximate. The best
known approximation factor for DST and SCSS is O(|T | ) for any fixed  >
0 [4]. On the other hand, the problems cannot be approximated to within a
factor of O(log2− n) for any  > 0, unless NP has quasi-polynomial time Las
Vegas algorithms [19]. For the most general DSN problem the best known ratio
is n2/3+ for any  > 0 and the problem cannot be approximated to within
1−
O(2log n ) for any  > 0, unless NP has quasi-polynomial time algorithms [1].
We refer to surveys, e.g., [24], for more information on the numerous polynomialtime approximation results for Steiner-type problems.
From the perspective of parameterized algorithms [6, 9] the problems are

2

mostly studied with respect to the number of terminals. It follows from the
classical result of Dreyfus and Wagner [10] (independently found by Levin [25]),
that Steiner Tree and also DST can be solved in O(3|T | · nO(1) ) time. The
algorithm was subsequently improved [11, 14, 2] with the latest algorithm of
Nederlof [28] achieving O(2|T | · nO(1) ) time and polynomial space complexity.
For the SCSS and DSN with q terminals and q terminal pairs, Feldman and
Ruhl [12] showed that the problems can be solved roughly in O(n2q ) and O(n4q )
time, respectively. We cannot expect fixed parameter tractability for these
problems, since the problems are W[1]-hard with respect to this parameter [17]
(and even with respect to the total size of the sought graph). In fact, unless
the Exponential Time Hypothesis (ETH) [21] fails, SCSS cannot be solved in
f (q)no(q/ log q) time on general graphs and DSN cannot be solved in f (q)no(q)
time even on planar DAGs [5]. Chitnis et al. [5]
also showed that on planar
√
q) O( q)
time, but it is still W[1]graphs SCSS can be solved within 2O(q log
n
√
hard and cannot be solved within f (q)no( q) time, unless ETH fails.
With respect to the less studied parameter “number of nonterminals in the
solution”, representing one possible measure of the solution size, all the problems
are on general graphs W[2]-hard by an easy reduction from Set Cover (see,
e.g., Guo et al. [17]). On planar graphs, only DST was studied with respect to
this parameter, achieving fixed parameter tractability [22].
Our Contribution In this paper our aim is to generalize the positive results
for DST and SCSS also to q-RST. Unfortunately, as our first result, we show
that q-RST is still too general to achieve this goal. Namely, we show that for
any constant q ≥ 2 the q-RST is W[1]-hard with respect to |T | even on directed
acyclic graphs and cannot be solved within f (|T |)no(|T |/ log |T |) time, unless ETH
fails. In fact the same results hold even if we replace |T | by (k + |T |), the total
number of vertices in the resulting subgraph (minus q).
Then, we restrict the problem further to its special case by requiring R ⊆ T .
In fact, for better readability we require the solution to provide a path from each
r ∈ R to each vertex t ∈ R ∪ T and assume T ∩ R = ∅. We call the resulting
problem q-Root Steiner Tree with Pedestal (q-RST-P). Observe that it
still generalizes DST as well as SCSS.
We show that we can generalize the algorithm of Feldman and Ruhl [12] for
SCSS to q-RST-P, using an algorithm for DST as a subroutine. The running
time of our algorithm is O(22q+4|T | · n2q+O(1) ), i.e., the problem is FPT with
respect to |T | for any constant q and the exponent of the polynomial depends
linearly on q. The lower bounds for SCSS indicate that this dependency on q
is optimal. In fact if T = ∅, then our algorithm is exactly the algorithm of
Feldman and Ruhl, while if q = 1, the algorithm boils down to a single call to
the DST subroutine.
The algorithm of Feldman and Ruhl is based on a token game, where the
tokens trace the path required in the solution. The solution of the instance is
then represented by a sequence of moves of the tokens between two specified
configurations. We first enrich the game by introducing new tokens that trace

3

the path to vertices of T while using the original tokens to trace paths between
the vertices in R. We call this game cautious.
We then show that the solutions can be represented by move sequences with
further interesting properties. these allow us to group the moves and reduce
the number of intermediate configurations. The resulting game, which we call
accelerated, has moves very similar to the original game of Feldman and Ruhl,
but each move is now equipped by a subset of vertices of T that is also reached
in this move. We use this similarity for further result in our paper.
The crucial property of the problem that allows us to come up with the
algorithm is that there is a vertex such that every path required by the solution
can be dragged through this specific vertex (allowing the vertices to repeat on
the path). To illustrate this, we introduce another variant of the problem qRoot Steiner Tree with Trunk (q-RST-T), which is the same as q-RST,
but the solution is further required to contain a vertex which has a path from
each vertex in R and to each vertex in T . We show that this problem can
be solved in similar running time as q-RST-P, namely O(22q+4|T | · n3q+O(1) ).
Qualitatively similar running time can be also achieved if the special vertex
provides all but a constant number of the paths required by the problem.
We further generalize the result of Chitnis et al. [5] giving the improved
algorithm for SCSS in planar graphs to obtain an algorithm
for q-RST-P in
√
planar graphs with running time O(2O(q log q+|T | log q) · nO( q) ).
While the hardness result applies to the decision variant, the algorithms
directly apply to the (cardinality) optimization case. Moreover, it is straightforward to generalize them to the case of vertex weights (we might want to use
different, more suitable, DST algorithm as a subroutine, based on the actual
range of the weights). In order to use arc weights, one just has to subdivide
each arc and give the weight of the arc to the newly created vertex. Thus our
algorithms also apply to vertex weighted and arc weighted variants of the problems. Nevertheless, for ease of presentation, we formulate all our results only
for the cardinality case.
Organization of the paper In Section 2 we present the hardness result for
the unrestricted version of q-RST. Section 3 describes the games and the algorithm for q-RST-P. This is generalized to q-RST-T in Section 4. The improved
algorithm for q-RST-P in planar graphs is contained in Section 5. We conclude
the paper with outlook in Section 6.

2

Unrestricted case

In this section we show that the unrestricted variant of q-RST is W[1]-hard with
respect to |T | even on directed acyclic graphs. Let us start with the case q = 2.
Theorem 1. 2-RST is W[1]-hard with respect to |T | even on directed acyclic
graphs. Moreover, there is no algorithm for 2-RST on directed acyclic graphs
|T |
running in f (|T |)no( log |T | ) time, unless ETH fails.
4

The rest of this section is devoted to the proof of this theorem. Our starting
point are known results for the following problem.
Partitioned Subgraph Isomorphism (PSI)
Input: Undirected graphs H = (VH , EH ) and G = (VG , EG ) and a coloring
function col : VH → VG .
Question: Is there an injection φ : VG → VH such that for every i ∈ VG ,
col(φ(i)) = i and for every {i, j} ∈ EG , {φ(i), φ(j)} ∈ EH ?
PSI is known to be W[1]-hard [29]. For the second part of the theorem we
need the following lemma by Marx [26].
Lemma 1 ([26, Corollary 6.3]). Partitioned Subgraph Isomorphism cano(

k

)

not be solved in f (k)VH log k time, where f is an arbitrary function and k = |EG |
is the number of edges in the smaller graph G, unless ETH fails.
We provide a parameterized reduction from PSI parameterized by |EG | to
2-RST parameterized by |T |.
Let (H = (VH , EH ), G = (VG , EG ), col) be an instance of PSI. To simplify
the description let us assume that there are some strict linear orders < on the
vertices in VH and in VG such that for every u and v with u < v we have
col(u) < col(v). We also assume that for every edge {u, v} ∈ Eh we have
{col(u), col(v)} ∈ EG as we can delete the edges not satisfying this condition
without affecting the answer to the instance. Finally, since the problem can be
solved for each connected component separately, we assume that G is connected
and has at least one edge.
We start by constructing the directed graph G0 = (V 0 , A0 ) (see also Fig. 1).
We let V 0 = R ∪ VH ∪ E 0 ∪ F ∪ T , where
R = {rV , rE },

E 0 = {au,v | {u, v} ∈ EH , u < v},

F = {bu,v , bv,u | {u, v} ∈ E}, and

T = {ti,j , tj,i | {i, j} ∈ EG , i < j}.

The set of arcs is constructed as follows. We add arcs from rV to all vertices
in VH and from rE to all vertices in E 0 . For every edge {u, v} where u < v, we
add the following set of arcs:
• an arc from au,v to bu,v and an arc from au,v to bv,u ,
• an arc from u to bu,v and an arc from v to bv,u , and
• an arc from bu,v to tcol(u),col(v) and an arc from bv,u to tcol(v),col(u) .
To finish the construction we let k 0 = 3|EG | + |VG |. Note that we have
|T | = 2|EG |, i.e., the new parameter depends linearly on the original one and
the constructed graph is a directed acyclic graph.

5

rV

rE
G0

u
v

G
1

w

au,v

au,w

2

H
u(1)

v(2)
bv,u

bu,v
w(2)

t1,2

bu,w

bw,u

t2,1

Figure 1: Illustration of the reduction in the proof of Theorem 1. The graphs
G and H are on the left, col is in the brackets for each vertex, and the graph
G0 is on the right.
We start the proof of correctness of the reduction by showing that if (H, G, col)
is a yes-instance of PSI, then (G0 , R, T, k 0 ) is a yes-instance of 2-RST. Let
φ : VG → VH be the injection witnessing that (H, G, col) is a yes-instance.
We let S = {φ(i) | i ∈ VG } ∪ {aφ(i),φ(j) , bφ(i),φ(j) , bφ(j),φ(i) | {i, j} ∈ EG , i < j}.
Then for every {i, j} ∈ EG , where i < j, we have col(φ(i)) = i, col(φ(j)) = j,
{φ(i), φ(j)} ∈ EH , and φ(i) < φ(j). Therefore the vertices rV , φ(i), bφ(i),φ(j) , ti,j
form a path from rV to ti,j in G0 [R ∪ S ∪ T ], the vertices rV , φ(j), bφ(j),φ(i) , tj,i
form a path from rV to tj,i , the vertices rE , aφ(i),φ(j) , bφ(i),φ(j) , ti,j form a path
from rE to ti,j , and the vertices rE , aφ(i),φ(j) , bφ(j),φ(i) , tj,i form a path from rE
to tj,i (here we use that col(φ(i)) = i, col(φ(j)) = j, and {φ(i), φ(j)} ∈ EH ).
Since |S| = |VG | + 3|EG | = k 0 , (G0 , R, T, k 0 ) is indeed a yes-instance of 2-RST.
To prove the other implication, let us assume that (G0 , R, T, k 0 ) is a yesinstance of 2-RST and S is the set witnessing it. As the vertices in F are the
only in-neighbors of vertices in T and each vertex in F has out-degree one, there
must be at least 2|EG | vertices of F in S. There is a directed path from au,v to
ti,j in G0 if and only if {i, j} = {col(u), col(v)}. Hence there must be a separate
vertex of E 0 in S for each edge of G. Similarly, there is a directed path from u
to ti,j in G0 if and only if i = col(u). Hence, there is a separate vertex of VH
in S for each vertex of G (note that G is connected and has at least one edge).
Therefore, as |S| ≤ 3|EG | + |VG |, the budget is tight and there are exactly that
many vertices from each of the sets.
For every i ∈ VG let φ(i) be the unique vertex u of VH ∩ S with col(u) = i.
We show that φ has the desired properties. First of all it is injective and
col(φ(i)) = i for every i ∈ VG by definition. Next, note that a vertex u ∈ S ∩ VH
is connected to a vertex bu0 ,v only if u0 = u. Furthermore, for each ti,j there
is a unique in-neighbor bu,v in S. Since there is a path from rV to each ti,j , it
6

follows that for every bu,v ∈ S we have u ∈ S ∩ VH , namely u = φ(col(u)).
Now each vertex in E 0 has out-degree at most 2 and each vertex of F has outdegree 1 in G0 [R ∪ T ∪ S]. Thus, in order for rE to reach all 2|EG | vertices in T ,
each of the |EG | vertices in E 0 ∩S must have out-degree 2 in G0 [R∪T ∪S], i.e., bu,v
is in S if and only if bv,u is. Hence, for every bu,v ∈ S we have also v ∈ S ∩VH . In
other words, for every {i, j} ∈ EG there is an edge {φ(i), φ(j)} ∈ EH , finishing
the correctness of the reduction.
Since the new parameter |T | is linear in the original |EG |, the theorem now
follows from the result of Pietrzak [29] and from Lemma 1.
The same holds also with respect to the parameter (|T | + k).
Corollary 1. q-RST is W[1]-hard with respect to |T | even on directed acyclic
graphs for every q ≥ 2. Moreover, there is no algorithm for q-RST on directed
|T |
acyclic graphs running in time f (|T |)no( log |T | ) for any constant q ≥ 2, unless

ETH fails.

Proof. It is enough to add q − 2 vertices to R, each having an arc only to rV .
It is easy to verify that this preserves the properties of the construction.

3

Restriction to Solutions with Pedestal

Having shown in the previous section that q-RST is still too general to allow
for the nice algorithms known for DST and SCSS, in this section we restrict
ourselves further. To this end, we modify the definition of our problem in the
sense that we do not require to obtain a path from each vertex of R only to
each vertex of T , but also to each other vertex of R.
q-Root Steiner Tree with Pedestal (q-RST-P)
Input: A directed graph G = (V, A), two subsets of its vertices R, T ⊆ V
with |R| = q.
Task: Find a minimum size of a set S ⊆ V such that in G[R ∪ S ∪ T ] there
is a directed path from r to t for every r ∈ R and every t ∈ R ∪ T .
Note that this variant of q-RST could be also modeled by requiring R ⊆ T .
However, to simplify the description, we assume R ∩ T = ∅.
Theorem 2. For every q ≥ 1 the problem q-RST-P is fixed-parameter tractable
with respect to |T |. Namely there is an algorithm solving it in O(22q+4|T | ·
n2q+O(1) ) time, where the constants hidden in the O() notations are independent
of |T | and q.
The rest of this section is devoted to the proof of this theorem.
The q-RST-P problem with the set T empty is exactly the SCSS problem
(with q terminals). This problem was shown to be polynomial time solvable
for every constant q by Feldman and Ruhl [12] using a modeling by a token
game. The cost of an optimal strategy for that game equals cost of the smallest
solution to the SCSS instance.

7

We first slightly modify this game to model the problem for arbitrary T in
Subsection 3.1. We show there that optimal strategies for this game have some
interesting properties which we can further use. Then, in Subsection 3.2, we
introduce a new game with more powerful moves which allows us to make many
moves of the original game at once. Finally, in Subsection 3.3, we show that the
optimal strategies for the new game can be computed in the claimed running
time.

3.1

Cautious Token Game

In this subsection we show how to modify the original token of Feldman and
Ruhl in order to model the q-RST-P problem. We fix a vertex r0 ∈ R and let
R0 = R \ {r0 }. For a solution S the graph G[R ∪ S ∪ T ] will contain a path
from r0 to t for each vertex t in R0 ∪ T . These paths together form an out-tree
rooted at r0 which is called the backward tree. Also there is a path from each of
the vertices in R0 to r0 , and these together form an in-tree rooted at r0 , called
the forward tree.
The game traces the two trees by having three types of tokens, where two
of them behave similarly. First, we have an F -token at each of the vertices of
R0 and this token moves forward along the arcs of graph G. Second, we have a
B-token at each vertex of R0 , moving backward against the direction of the arcs
of G. The third type of tokens we use (in difference to Feldman and Ruhl) are
D-tokens which are originally placed one on each of the vertices of T and move
similarly as B-tokens.
The purpose of the tokens is to trace the forward and backward tree. Hence,
whenever two tokens of the same type arrive at the same vertex we can merge
them to one token. This is also the case for B-tokens and D-tokens, and in
case a B-token merges with a D-token we let the merged token be a B-token.
The purpose of introducing the D-tokens is to show that these are somewhat
less important for the game than B-tokens and, hence, they can be treated in a
different way in the new game we will introduce in the next subsection.
The state of the game can be described by tree subset of vertices (F, B, D)
representing the set of vertices occupied by F -tokens, B-tokens, and D-tokens,
respectively. Note that |F | ≤ q, |B| ≤ q, |D|
 ≤ |T | during the
 whole game.
V
V
V
Hence we take F, B ∈ ≤q
and D ∈ ≤|T
(here
and
on
|
≤q is the set of
subsets of V of size at most q).
The allowed moves are the following:
(1) Single moves
 for respective
 tokens: For every arc (u, v) ∈ A and all sets
V
V
F, B ∈ ≤q
and D ∈ ≤|T
| we introduce the following moves:
c

(a) If u ∈ F , then we have a move (F, B, D) →
− ((F \ {u}) ∪ {v}, B, D),
where the cost c of the move is 1 if v ∈
/ F ∪ B ∪ D and 0 otherwise.
c

(b) If v ∈ B, then we have a move (F, B, D) →
− (F, (B \{v})∪{u}, D \{u}),
where the cost c of the move is 1 if u ∈
/ F ∪ B ∪ D and 0 otherwise.
8

c

(c) If v ∈ D, then we have a move (F, B, D) →
− (F, B, (D\{v})∪({u}\B)),
where the cost c of the move is 1 if u ∈
/ F ∪ B ∪ D and 0 otherwise.


V
V
(2) Flipping: For all sets F, B ∈ ≤q
and D ∈ ≤|T
| we introduce the following
moves:
(a) if F 0 ⊆ F , B 0 ⊆ B, D0 ⊆ D, f ∈ F 0 , and b ∈ B 0 , then we have a move
c
(F, B, D) →
− ((F \ F 0 ) ∪ {b}, (B \ B 0 ) ∪ {f }, D \ (D0 ∪ {f })), where c
is the number of vertices on a shortest walk from f to b going through
all vertices in F 0 ∪ B 0 ∪ D0 . Here each vertex is counted each time it is
visited, but vertices in F 0 ∪ B 0 ∪ D0 are counted once less.

(b) if F 0 ⊆ F , B 0 ⊆ B, B 0 6= ∅, D0 ⊆ D, f ∈ F 0 , and d ∈ D0 , then we have
c
a move (F, B, D) →
− ((F \ F 0 ) ∪ {d}, (B \ B 0 ) ∪ {f }, D \ (D0 ∪ {f })),
where c is the number of vertices on a shortest walk from f to d going
through all vertices in F 0 ∪ B 0 ∪ D0 . Here, again, each vertex is counted
each time it is visited, but vertices in F 0 ∪ B 0 ∪ D0 are counted once
less.
(c) if F 0 ⊆ F , D0 ⊆ D, f ∈ F 0 , and d ∈ D0 , then we have a move
c
(F, B, D) →
− ((F \ F 0 ) ∪ {d}, B, (D \ D0 ) ∪ ({f } \ B)), where c is the
number of vertices on a shortest walk from f to d going through all
vertices in F 0 ∪ D0 . as in the previous cases, each vertex is counted
each time it is visited, but vertices in F 0 ∪ D0 are counted once less.
The original game of Feldman and Ruhl has only three types of moves: Single
moves for F -tokens (exactly as (1-a)), single moves for B-tokens (similar as (1b) and (1-c)) and flipping (all of (2)). If we did not distinguish the B-tokens
and D-tokens (and consider all of them as B-tokens, we would get exactly this
three types of moves. We make use of this fact in the proof of the equivalence of
costs of optimal strategies for this game and sizes of solutions for the q-RST-P
instance.
We distinguish the B- and D-tokens since we aim to show, e.g., that there
is an optimal strategy for the game not using any moves of type (2-c). During
the whole game the moves ensure that the invariant D ∩ B = ∅ is maintained.
This could be easily achieved by taking D = D \ B after each move, however, we
prefer to be more specific in taking out only the vertices which could actually
newly appear in the intersection.
Now we would like to claim, that the game represents the instance (G, R, T )
of q-RST-P. Namely, that the minimum size of a solution to (G, R, T ) is exactly
one less than the minimum cost of moves to get from (R0 , R0 , T ) to ({r0 }, {r0 }, ∅)
in the cautious token game. The easier direction is summarized by the following
lemma (see also Lemma 3.1 of [12]):
Lemma 2. If there is a move sequence from (R0 , R0 , T ) to ({r0 }, {r0 }, ∅) of total
cost c, then there is a set S ⊆ V of size at most c − 1 such that in G[R ∪ S ∪ T ]
there is a directed path from r to t for every r ∈ R and every t ∈ R ∪ T .
Moreover, given the sequence, the corresponding set S is easy to find.
9

The proof of this lemma follows from the definition of the moves of the game.
If we let S be the set of newly encountered vertices in the moves of the sequence
excluding r0 we get |S| + 1 ≤ c, as the cost of each move is an upper bound on
the number of newly encountered vertices including r0 .
The next lemma provides the counterpart. Let us call a move of type (2)
path-driven, if the minimum size walk in the definition of the cost of the move
can be taken as a simple path.
Lemma 3. If there is a set S ⊆ V of size at most c−1 such that in G[R ∪S ∪T ]
there is a directed path from r to t for every r ∈ R and every t ∈ R ∪ T , then
there is a move sequence from (R0 , R0 , T ) to ({r0 }, {r0 }, ∅) of total cost at most c
in which all type (2) moves are path-driven.
The lemma can be proved using exactly the same arguments as for the proof
of Lemma 2.2 in [12] (ignoring the difference between B- and D-tokens). The
aim is to construct a move sequence, where all intermediate position of tokens
are in H = G[R ∪ S ∪ T ].
Since each vertex is counted each time it becomes newly occupied by a token
and we want to find a move sequence of cost c, we cannot afford to re-occupy a
previously abandoned vertex. Specifically, we enforce the following rule:
Once a token moves off a vertex, no other token will ever move to
that vertex again.

(?)

A vertex is called “dead” once a vertex moves from it and the tokens can only
move to vertices which are still “alive”. Note specifically that a token may be
standing on a vertex that is already dead.
The sequence is constructed in a greedy fashion, maintaining the following
invariant:
There are paths using only alive vertices (except for endpoints)
from each vertex of F to r0 and from r0 to each vertex of B ∪ D.

(∗)

This is actually the only assumption used in the correctness proof of Feldman
and Ruhl to show that there is always a move to continue with, maintaining the
properties (?) and (∗) (see the proof of Lemma 3.2 and Section 4 of [12]). Since
there is always a move to continue and no token can return to a vertex it has
already visited, we must reach ({r0 }, {r0 }, ∅) at some point and the cost cannot
exceed c.
Since we aim on more detailed analysis of the game graph, we repeat some
notions and lemmata used in the correctness proof given by Feldman and Ruhl.
We say that a token t requires a vertex v if all legal paths for t to get to r0
go through v. Here a legal path is a path in the right direction given by token t,
within H, and using only alive vertices. We will further refer to a token and to
the vertex it is currently standing on exchangeably, e.g., we say that a token t
requires a token t0 if t requires the vertex t0 is currently standing on. Note that
we can move the tokens using type (1) moves as long as they are not required
by any other token. If each token is required by some other token, then the
following holds.
10

Lemma 4 (Flip Lemma, Lemma 3.3 of [12]). Let the F0 -tokens be the F -tokens
that are not required by any other F -token. Similarly, let B0 -tokens be the Band D-tokens, that are not required by any other B- or D-token. Suppose that
every token is required by some other token. Then there is an F0 -token f and a
B0 -token b such that
• f requires b, and no other F0 -token requires b, and
• b requires f , and no other B0 -token requires f .
Let f and b be as in the flip lemma and P be a simple path between them
in H using only alive vertices. Then we have the following claim.
Claim 1 (Claim 3.4 of [12]). All tokens that require a vertex on P are on P
themselves.
If F 0 , B 0 , and D0 are the sets of F -, B-, and D-tokens on P , respectively,
then we can apply type (2) move, preserving the property (∗).
Since this is the only place where type (2) moves are used in the construction
of the move sequence, we may assume that whenever a move of type (2) is used,
it is used on the specific vertices f and b as selected by the flip lemma. Note that
in this case the shortest walk from f to b going through all vertices in F 0 ∪B 0 ∪D0
is actually a simple path, i.e., all type (2) moves are path-driven. However, since
it is complicated to test for the existence of such a path, following Feldman and
Ruhl, we introduced more moves, which does not hurt the construction.
Our aim now is to show that the moves of type (2-c) can be omitted without
affecting the correspondence between the game and the instance of q-RST-P.
Lemma 5. If there is a set S ⊆ V of size at most c−1 such that in G[R ∪S ∪T ]
there is a directed path from r to t for every r ∈ R and every t ∈ R ∪ T , then
there is a move sequence from (R0 , R0 , T ) to ({r0 }, {r0 }, ∅) of total cost at most
c in which all type (2) moves are path-driven and, moreover, there are no moves
of type (2-c).
Proof. Let H = G[R∪S ∪T ] and let H ∗ be an edge minimal subgraph of H such
that there is a directed path from r to t for every r ∈ R and every t ∈ R ∪ T .
Let us construct the sequence greedily as in the proof of Lemma 3 and suppose
for contradiction that at some point a type (2-c) is to be applied on f , d, F 0 ,
and D0 . That is, there is a path P from f to d in H ∗ , F 0 and D0 are the sets of
F - and D-tokens on P , respectively, and there are no B-tokens on P .
Now suppose that one of the tokens merged into the token f started its tour
on a vertex s of R0 , i.e., there is a path in H ∗ from s to f using only dead
vertices (except for f ) (see also Fig. 2). Let bs be the B-token that also started
its tour on s. Since bs is not on P and, hence, does not require f by Claim 1,
there is a path from r0 to s in H ∗ that avoids f . Note specifically that f 6= s, as
this would mean that s is required by d, bs stayed on s and hence on P . Since f
requires d, there is a path of alive vertices from d to r0 . Similarly, as d requires
f , there is a path of alive vertices from r0 to f . Let a be the last arc on that
path. Note that it connects two alive vertices.
11

s

bs

s0

t

f

d

a
r0

Figure 2: Illustration of the situation in the proof of Lemma 5. The arrows
denote paths and those dashed are formed by dead vertices.
We claim that in Ĥ = H ∗ \ {a} there is also a directed path from r to t for
every r ∈ R and every t ∈ R ∪ T , contradicting the minimality of H ∗ . In fact
we will only show that there is a path in Ĥ from r0 to each t ∈ R0 ∪ T and from
each r in R0 to r0 . Such path are definitely present in H ∗ . If they avoid f , then
they are still present in Ĥ. If some of the paths cannot avoid f in Ĥ, then the
corresponding token t in the game for H ∗ starting at vertex s0 requires f . It
follows that t lies on P and there is a path between s0 and t in the direction
appropriate for the token formed by dead vertices (except for t). We know that
t is not a B-token, as there are no such tokens on P . If it is an F -token, then
we can obtain a path from t to r0 avoiding a by concatenating the part of P to
d and a path from d to r0 . If t is a D-token, then we can obtain a path from r0
to t in H ∗ by shortcutting the walk obtained by concatenating the path from r0
to s (avoiding f ), the path from s to f (dead), and a part of P (not containing
a).
Hence, indeed, if H ∗ is minimal, then every type (2) move is of type (2-a)
or (2-b).
Lemma 5 shows, that there are no flips, that would result in a D-token on
a new position. We aim to show that D-tokens interact with the other tokens
even less. Namely, if a D-token meets with an F -token, then it stays on place
until it is merged with some B-token. We show that by making a side step and
considering the game on a modified graph. To this end we need a following
definition (see also Fig. 3).
Definition 1. Let G = (V, A) be a directed graph. A forking of G is the
directed graph Y(G) = (V̂ , Â), where
V̂ = V × {0, 1} and

Â = {((u, 0), (v, 1)) | (u, v) ∈ A} ∪ {((v, 1), (v, 0)) | v ∈ V }.
12

u

G

w

v

Y(G)

(u, 1)
(u, 0)

(v, 1)

(v, 0)

(w, 1)

(w, 0)

Figure 3: Illustration of the Definition 1—graph G on left and Y(G) on right.
There is a natural correspondence between paths in G and paths in Y(G),
namely a path P in G correspond to a path Y(P ) in Y(G). Let us set R̂ =
{(r, 0) | r ∈ R} and T̂ = {(t, 0) | t ∈ T }. We relate the solution in the forking
of G to solution in G by the following easy lemma.
Lemma 6. Let G = (V, A) be a directed graph, R, T ⊆ V , R ∩ T = ∅, and
Y(G) = (V̂ , Â) its forking. There is a solution S ⊆ V \ (R ∪ T ) of size at most k
for (G, R, T ) if and only if there is a solution Ŝ ⊆ V̂ of size at most 2k + |R ∪ T |
for (Y(G), R̂, T̂ ).
Proof. If S is a solution for (G, R, T ) of size k, then let Ŝ = (S ∪ R ∪ T ) × {0, 1} \
(R̂ ∪ T̂ ). It is easy to verify, that Ŝ is a solution for (Y(G), R̂, T̂ ) of size at most
2k + |R ∪ T |.
For the other direction, suppose Ŝ is a solution for (Y(G), R̂, T̂ ) of size at
most 2k + |R ∪ T |. If there is v ∈ V \ (R ∪ T ) such that |Ŝ ∩ ({v} × {0, 1})| = 1,
then the vertex in the intersection is either a sink or a source, as there are no
arcs from (v, 1) and no arcs to (v, 0) except for ((v, 1), (v, 0)). In both cases
Ŝ \ {(v, 0), (v, 1)} is also a solution for (Y(G), R̂, T̂ ). Also note that since there
is a path to every vertex in R̂ ∪ T̂ in Y(G)[R̂ ∪ Ŝ ∪ T̂ ], we have (R ∪ T ) × {1} ⊆ Ŝ.
Hence we can assume that R̂ ∪ Ŝ ∪ T̂ = (R ∪ S ∪ T ) × {0, 1} for some S ⊆ V of
size at most k. It is easy to verify that this S forms a solution for (G, R, T ).
Now consider the token game for the forking of G, R̂, and T̂ and suppose
that there is a solution Ŝ for (Y(G), R̂, T̂ ) of size at most 2k + |R ∪ T |. By
Lemma 5, there is a sequence M of moves from (R̂ \ {(r0 , 0)}, R̂ \ {(r0 , 0)}, T̂ )
to ({(r0 , 0)}, {(r0 , 0)}, ∅) of total cost 2k + |R ∪ T | + 1 without moves of type
(2-c).
We want to show that the following claim.
Claim 2. If there is a vertex v ∈ V such that at some point in the move sequence
a D-token and an F -token each occupy a vertex in {v} × {0, 1}, then the next
move touching the D-token is either of type (2), or single-move (type (1)) of
some B-token merging with the D-token.
Proof. First of all if the tokens actually meet on the same vertex, say (v, i),
then at least one of the tokens must have used the arc ((v, 1), (v, 0)) and the
vertex (v, 1 − i) is dead. This, however, contradicts the property (∗) for the
other token. Now suppose there is an F -token on (v, 1) and a D-token on (v, 0).

13

Since a type (2-a) or (2-b) moves do not place D-tokens on vertices where they
were not previously, the previous move touching the D-token was of type (1).
Therefore, before the move, the D-token was on (v, 1). If the F -token was not
there before that move, then the property (?) is violated, otherwise they meet
at the vertex (v, 1) which is not possible as we have already shown. Finally, if
there is an F -token on (v, 0) and a D-token on (v, 1), then the tokens require
each other and, therefore, no single move can be applied to any of them. Thus
the claim follows.
We have shown that there is an optimal move sequence from (R̂\{(r0 , 0)}, R̂\
{(r0 , 0)}, T̂ ) to ({(r0 , 0)}, {(r0 , 0)}, ∅) with the property given by the claim. Now
we want to show, that this move sequence can be translated to an optimal move
sequence from (R \{r0 }, R \{r0 }, T ) to ({r0 }, {r0 }, ∅) in the original graph, with
the property given by the claim.
We achieve that by simply projecting everything to the first coordinate.
I.e., let us replace single moves for arcs ((u, 0), (v, 1)) by single moves for the
arc (u, v) and omit single moves for arcs ((v, 1), (v, 0)). If there is a flip move
with the path being just the arc ((v, 1), (v, 0)) for some v, then we just omit it.
If the path is longer, we replace the flip by a flip on the projection of the path
and with the projections of the sets F 0 , B 0 , D0 .
We should verify that this produces a valid move sequence. It is enough
to show that the property (?) is not violated, the property (∗) then follows.
Suppose that some token leaves the vertex v before some other vertex enters
it. But this would mean that in Y(G), a token leaves (v, i) before some other
token enters (v, 1 − i). However, as each token has to visit both vertices (v, i)
and (v, 1 − i) this would violate the property (?) also in the graph Y(G).
Finally, note that the produced sequence has still the property that it contains no (2-c) moves, and, whenever an F -token meets with a D-token on a
vertex, then the next move touching the D-token is either of type (2), or singlemove (type (1-b)) of some B-token merging with the D-token. This is not
affected by omitting some of the flips as there are no moves of type (2-c). In
other words, the vertex must stay alive until the D-token is touched and, hence,
the F -token will not be touched before the D-token is touched, except possibly
by type (1-a) moves of other F -tokens merging with the current one.
Move sequences with these properties allow us to postpone the moves of
the D-tokens just before the move in which these tokens are merged with some
B-token. This is a crucial property we use in the accelerated game.
We formulate the obtained results as a lemma.
Lemma 7. If there is a solution S ⊆ V of size at most c − 1 for (G, R, T ),
then there is a move sequence from (R0 , R0 , T ) to ({r0 }, {r0 }, ∅) of total cost at
most c in which all type (2) moves are path-driven and, moreover, there are no
moves of type (2-c). Furthermore, in this sequence of moves, whenever after
some move an F -token and a D-token sit together on a vertex v ∈ V , then the
next move touching the D-token is either of type (2), or single-move (type (1-b))
of some B-token merging with the D-token.

14

3.2

Accelerated Token Game

In the accelerated game the D-tokens stay at their places until the move in
which they should be merged with a B-token. The moves then also include the
costs of moving the D-tokens from their original places to the vertex where they
get merged with the B-token. Therefore, we now represent the positions of the
D-tokens only as subsets of T .
To define the costs of the moves we use the following notion. Let ST (r, X)
be the minimum number of vertices in a set S such that in G[{r} ∪ X ∪ S] there
is a path from r to every x ∈ X. I.e., this is a variation of DST with root r and
terminals X.
We have the following moves (we number the moves from (3), as not to
confuse them with the moves of the cautious game).

V
(3) Single moves: For every arc (u, v) ∈ A and all sets F, B ∈ ≤q
and D ⊆ T
we introduce the following moves:
c

(a) If u ∈ F , then we have a move (F, B, D) →
− ((F \ {u}) ∪ {v}, B, D),
where the cost c of the move is 1 if v ∈
/ F ∪ B ∪ D and 0 otherwise.
c

(b) If v ∈ B and D0 ⊆ D then we have a move (F, B, D) →
− (F, (B \
{v}) ∪ {u}, D \ (D0 ∪ {u})), where the cost c is ST (u, D0 ∪ {v}) + 1 if
u∈
/ F ∪ B ∪ D and ST (u, D0 ∪ {v}) otherwise.

V
(4) Flipping: For all sets F, B ∈ ≤q
and D ⊆ T we introduce the following
moves:
(a) if F 0 ⊆ F , B 0 ⊆ B, D0 ⊆ D, f ∈ F 0 , and b ∈ B 0 , then we have a move
c
(F, B, D) →
− ((F \ F 0 ) ∪ {b}, (B \ B 0 ) ∪ {f }, D \ (D0 ∪ {f })), where c is
as described below.
(b) if F 0 ⊆ F , B 0 ⊆ B, B 0 6= ∅, D0 ⊆ D, D0 6= ∅, f ∈ F 0 , and v is an
c
arbitrary vertex in V \ B, then we have a move (F, B, D) →
− ((F \ F 0 ) ∪
0
0
{v}, (B \ B ) ∪ {f }, D \ (D ∪ {f })), where c is as described below.
c

(5) Finishing: For all sets D ⊆ T we have a move ({r0 }, {r0 }, D) →
− ({r0 }, {r0 }, ∅),
where c = ST (r0 , D).
Let us now explain the intuition behind the moves. It is clear for (3-a). We
consider the move (3-b) to move the B-token from v as well as the D-tokens
from D0 to u. The move (4-a) moves all B- and D-tokens from B 0 ∪ D0 to f
at the same time moving the F -tokens from F 0 to b. The move (4-b) does the
same thing, except that the F -tokens are taken to a vertex v. The move (5)
moves the D-tokens from D to r0 .
We would like to define the cost of moves of type (4) as the minimum number
of vertices in a subgraph that provides a walk from f to b (or from f to v) through
all vertices in F 0 ∪ B 0 and at the same time a path from f to each vertex of D0 ,
where the vertices in F 0 ∪ B 0 ∪ D0 again do not count. In fact the solution will
again use this type of moves only when there is a simple path from f to b (or
from f to v) through all vertices in F 0 ∪ B 0 .
15

As this condition is complicated to test and the desired cost is complicated
to compute, we will define a cost of a move which provides an upper bound on
the desired cost, and coincides with the desired cost whenever the optimal walk
is actually a simple path.
We define the cost of the type (4-a) moves c to be the minimum over all
bijections φ : {2, . . . , |F 0 ∪ B 0 | − 1} → (F 0 ∪ B 0 ) \ {f, b} (representing the order
of the vertices of (F 0 ∪ B 0 ) \ {f, b} along the walk) and all mappings ψ : D0 →
(F 0 ∪B 0 )\{b} (representing the part of the path at which the particular D-token
P|F 0 ∪B 0 |−1
joins it) of the sum i=1
ST (φ(i), ψ −1 (φ(i)) ∪ {φ(i + 1)}), where φ(1) = f
0
0
and φ(|F ∪ B |) = b.
Similarly, the cost of a (4-b) move is the minimum over all bijections φ :
{2, . . . , |F 0 ∪ B 0 |} → (F 0 ∪ B 0 ) \ {f } and all mappings ψ : D0 → (F 0 ∪ B 0 ) of the
P|F 0 ∪B 0 |
sum i=1
ST (φ(i), ψ −1 (φ(i))∪{φ(i+1)}), where φ(1) = f and φ(|F 0 ∪B 0 |) =
v. Here, the cost is increased by one if v ∈
/ (D ∪ F ).
We are going to show that solving the instance of q-RST-P again corresponds
to finding a cheapest possible move sequence from (R0 , R0 , T ) to ({r0 }, {r0 }, ∅)
in the accelerated token game.
Again, it is easy to see that if there is a move sequence, then there is a
solution of the corresponding cost.
Lemma 8. If there is a move sequence of the accelerated game from (R0 , R0 , T )
to ({r0 }, {r0 }, ∅) of total cost c, then there is a solution S ⊆ V for (G, R, T ) of
size at most c − 1.
As in the previous cases, given the move sequence, the solution can be obtained as a union of the vertex sets witnessing the costs of particular moves.
Let us now focus on the more complicated direction of the equivalence.
Lemma 9. If there is a solution S ⊆ V for (G, R, T ) of size at most c −
1, then there is a move sequence of the accelerated game from (R0 , R0 , T ) to
({r0 }, {r0 }, ∅) of total cost at most c.
Proof. By Lemma 7 there is a move sequence M for the cautious game from
(R0 , R0 , T ) to ({r0 }, {r0 }, ∅) of total cost at most c, which, moreover, does not
use moves of type (2-c) and such that whenever after some move an F -token
and a D-token sit together on a vertex v ∈ V , then the next move touching
the D-token is either of type (2), or single-move (type (1-b)) of some B-token
merging with the D-token.
We construct a move sequence M 0 for the accelerated game based on the
sequence M . We construct the sequence from the start to end and during the
process we keep updated a variable Dvar representing the remaining unmoved
D-tokens. Initially it is set to T . Let us take the moves of the sequence M one
by one. While the moves of type (1-a), (1-b), (2-a), and (2-b) are immediately
translated to moves of M 0 with the same sets F and B, the moves of type (1-c)
are postponed and included in the next move of other type that touches the
particular token.

16

Since we want to show that the sequence M 0 has also cost at most c, we
charge some vertices to pay the cost of the move currently added to M 0 . These
are always the vertices newly occupied and sometimes some more vertices which
we turn dead. Each vertex in S ∪ {r0 } can pay only once during the game and
only a cost of 1. We will show at the end that this condition is not violated.
If there is a (1-a) move (F, B, D) → (F 0 , B, D) in M , then we put into M 0 a
(3-a) move (F, B, Dvar ) → (F 0 , B, Dvar ). If the cost of the move is 1, then we
charge the unique vertex in F 0 \ F .
If there is a (1-b) move (F, B, D) → (F, B 0 , D0 ) for arc (u, v), then let Dv ⊆ T
be the set of original locations of the D-tokens merged (by (1-c) moves) into the
B-token on v since it was placed there. Also, if u ∈ D, then let Du ⊆ T be the
set of original locations of tokens merged into the D-token on v. Otherwise let
Du = ∅. We put into M 0 the (3-b) move (F, B, Dvar ) → (F, B 0 , Dvar \(Dv ∪Du ))
and update Dvar to Dvar \ (Dv ∪ Du ).
We charge the vertices involved in the (1-c) moves moving the D-tokens
from Dv to v and from Du to u, except for Du ∪ Dv ∪ {v}. The vertex u is only
charged if u ∈
/ F ∪ B ∪ Dvar . Note that this way we did not charge any vertex of
F ∪ B ∪ Dvar as, due to the properties of M , the D-tokens can only meet the Bor F -tokens in v or u, and all D-tokens which would merge with the D-tokens
considered are also considered. Since the charged vertices together with vertices
in F ∪ B ∪ Dvar provide paths from u to all vertices in (Dv ∪ Du ∪ {v}), it
follows that the number of charged vertices is at least ST (u, Dv ∪ Du ∪ {v}) + 1
if u ∈
/ F ∪ B ∪ Dvar and ST (u, Dv ∪ Du ∪ {v}) otherwise.
If there is a (1-c) move in M , then we skip it and put no new moves into M 0
at the moment.
For a (2-a) move (F, B, D) → ((F \ F 0 ) ∪ {b}, (B \ B 0 ) ∪ {f }, D \ (D0 ∪ {f }))
in M let us do the following. For each v ∈ (D0 ∪ {f }) let Dv ⊆ T be the set
of original locations of the D-tokens merged into the token on v. Similarly, for
each v ∈ B 0 let Dv ⊆ T be the set of original locations of the S
D-tokens merged
into the B-token on v since it was placed there. We let D00 = v∈D0 ∪B 0 ∪{f } Dv
(note that the union is disjoint). We put into M 0 the (4-a) move
(F, B, Dvar ) → ((F \ F 0 ) ∪ {b}, (B \ B 0 ) ∪ {f }, Dvar \ D00 ).
Then we update Dvar to Dvar \ D00 .
To charge some vertices for the cost of the move, let P be the path driving
the cost of the (2-a) move and ` = |F 0 ∪ B 0 |. Let φ : {1, . . . , `} → (F 0 ∪ B 0 ) be
the order of the vertices in F 0 ∪ B 0 along P from f to b. That is φ(1) = f , φ(2)
is the next vertex from F 0 ∪ B 0 along the path etc. For each i ∈ {1, . . . , ` − 1}
let Pi be the vertices on P between φ(i) and φ(i + 1) and Xi0 be union over
v ∈ (Pi ∪ {φ(i)}) ∩ (D0 ∪ B 0 ∪ {f }) of the sets of vertices involved in the (1-c)
moves in M moving the D-tokens from Dv to v. Let X`0 be the set of vertices
involved in the (1-c) moves in M moving the D-tokens from Db to b. For each
0
i ∈ {1, . . . , ` − 2} let Xi = Xi0 ∪ Pi and let X`−1 = X`−1
∪ X`0 ∪ P`−1 . We charge
S`−1
all vertices in i=1 Xi except for vertices in F 0 ∪ B 0 ∪ D00 . Note again that the
union is disjoint.
17

We should show that the number of charged vertices is at least the cost of
the move. Let us define a mapping ψ : D00 → (F 0 ∪ B 0 ) \ {b} as follows. For
each i ∈ {1, . . . , ` − 1}, each v ∈ (Pi ∪ {φ(i)}) ∩ (D0 ∪ B 0 ), and each d ∈ Dv
let ψ(d) = φ(i) and for each d ∈ Db let ψ(d) = φ(` − 1). Since for each
i ∈ {1, . . . , ` − 1}, the vertices in Xi ∪ {φ(i), φ(i + 1)} ∪ ψ −1 (φ(i)) provide a path
from φ(i) to each vertex in ψ −1 (φ(i)) ∪ {φ(i + 1)}, we have |Xi \ ({φ(i), φ(i +
1)} ∪ ψ −1 (φ(i)))| ≥ ST (φ(i), ψ −1 (φ(i)) ∪ {φ(i + 1)}) and the number of charged
vertices is at least the cost of the move.
For a (2-b) move we proceed similarly as for (2-a) moves with small differc
ences. Let (F, B, D) →
− ((F \ F 0 ) ∪ {d}, (B \ B 0 ) ∪ {f }, D \ (D0 ∪ {f })) the (2-b)
move in M . For each v ∈ (D0 ∪{f }) let Dv ⊆ T be the set of original locations of
the D-tokens merged into the token on v. Similarly, for each v ∈ B 0 let Dv ⊆ T
be the set of original locations of the D-tokens
merged into the B-token on v
S
since it was placed there. We let D00 = v∈D0 ∪B 0 ∪{f } Dv (the union is disjoint).
We put into M 0 the (4-b) move
(F, B, Dvar ) → ((F \ F 0 ) ∪ {d}, (B \ B 0 ) ∪ {f }, Dvar \ D00 ),
i.e., the move is performed with d in the role of v. Then we update Dvar to
Dvar \ D00 .
To charge some vertices for the cost of the move, let P be the path driving the
cost of the (2-b) move and ` = |F 0 ∪B 0 ∪{d}|. Let φ : {1, . . . , `} → (F 0 ∪B 0 ∪{d})
be the order of the vertices in F 0 ∪ B 0 ∪ {d} along P from f to d. The sets Pi ,
Dv , and Xi0 are defined the same way as for the (2-a) moves and X`0 is the set
of vertices involved in the (1-c) moves in M moving the D-tokens from Dd to
d. S
We define the sets Xi the same way as before and again charge all vertices
`−1
in i=1 Xi except for vertices in F 0 ∪ B 0 ∪ D0 . The vertex d is charged if and
only if it is not in D ∪ F .
We should again show that the number of charged vertices is at least the
cost of the move. Let us define the mapping ψ : D00 → (F 0 ∪ B 0 ) \ {d} the same
way as above. Specifically, for each d0 ∈ Dd let ψ(d0 ) = φ(` − 1). Since for
each i ∈ {1, . . . , ` − 1}, the vertices in Xi ∪ {φ(i), φ(i + 1)} ∪ ψ −1 (φ(i)) again
provide a path from φ(i) to each vertex in ψ −1 (φ(i)) ∪ {φ(i + 1)}, we have
|Xi \ ({φ(i), φ(i + 1)} ∪ ψ −1 (φ(i)))| ≥ ST (φ(i), ψ −1 (φ(i)) ∪ {φ(i + 1)}) and the
number of charged vertices is at least the cost of the move.
Finally, if the whole sequence was processed and Dvar 6= ∅, then we add at
the end of the sequence M 0 a type (5) move ({r0 }, {r0 }, Dvar ) → ({r0 }, {r0 }, ∅)
and charge the vertices involved in the (1-c) moves in M moving the D-tokens
from Dvar to r0 except from vertices in Dvar and r0 .
It remains to show that each vertex is charged at most once. For that purpose
we distinguish the vertices only used by D-tokens and the vertices also used by
an F - or B-token. Observe that the tokens use exactly the same vertices in the
sequence M 0 as in M . If two D-tokens used the same vertex not used by F or B-tokens, then these were merged together in M and hence processed in the
same move in M 0 , therefore the vertex was only charged once.
Among the vertices used by an F - or B-token the move of M 0 always charges
18

the vertices newly occupied by such tokens and those turned dead by the corresponding move of M without being previously occupied by an F - or B-token.
Since each vertex gets newly occupied by an F - or B-token at most once and
only if it is not dead and can be turned dead only once in M , it follows that
each vertex is charged at most once.

3.3

The Algorithm

The algorithm first computes the so-called “game graph” for the accelerated
game. The vertex set V 0 of this directed graph is formed by all possible configu-
V
rations of the tokens in the game, i.e., by all triples (F, B, D), where F, B ∈ ≤q
0
and D ⊆ T . The arcs A of this graph correspond to legal moves of the accelerated game, i.e., moves of type (3),(4), and (5). The length of each arc is equal
to the cost of the corresponding move of the game.
Once the game graph is constructed, we simply find the shortest path from
the vertex (R0 , R0 , T ) to the vertex ({r0 }, {r0 }, ∅). Since each arc of the graph
corresponds to a move of the game, the shortest path corresponds to an optimal
sequence of moves to get from the configuration (R0 , R0 , T ) to the configuration
({r0 }, {r0 }, ∅). By Lemmata 8 and 9 such a sequence of cost c exists if and only
if there is a solution of size c − 1 for the instance (G, R, T ) of q-RST-P.
To bound the running time of the algorithm, let us first focus on computing
the costs of the moves. For that purpose we often need to compute ST (r, X).
To this end we can use the algorithm of Nederlof [28] running in O(2|X| · nO(1) )
time (see also Misra et al. [27, Lemma 2]).

n 2
The game graph has at most ≤q
· 2|T | = O(n2q · 2|T | ) vertices. There
are at most O(n2q−1 · m · 2|T | ) moves of type (3-a) and at most n2q−1 · m · 3|T |
moves of type (3-b) in total (each vertex of T can be either in T \ D, in D \ D0 ,
or in D0 ). Computing the cost of a (3-a) move is trivial and can be done in
O(q + |T |) time. For (3-a) move we need to run the algorithm of Nederlof once,
which takes O(2|T | · nO(1) ) time.
Concerning type (4) moves, for each vertex (F, B, D) there are at most 2|F | ·
|F | · 2|B| · |B| · 2|D| moves of type (4-a) and at most 2|F | · |F | · 2|B| · (n − |B|) · 2|D|
moves of type (4-b). This gives at most O(n2q+1 · 22|T | 22q ) of them in total.
To compute the cost of a type (4) move, we may use dynamic programming
of Held-Karp type [20]. Let us describe it in more detail for type (4-a) move. We
introduce one table indexed by subsets J of F 0 ∪ B 0 which are proper supersets
of {f }, a vertex j from J \ {f } and a subset D00 of D0 . The semantic meaning
is that we compute the cost as if only the vertices in J and D00 were involved
in the move and the F -tokens from J ended in vertex j.
The table is initialized by setting the entries indexed by ({f, j}, j, D00 ) to
ST (f, D00 ∪ {j}). Then we fill the table according to the size of J starting from
the smallest sets. For every J, with |J| > 2, j ∈ J \ {f }, and D00 ⊆ D0 we set
the entry indexed by (J, j, D00 ) to the minimum over all j 0 ∈ J \ {j, f } and all
subsets D̄ of D00 of the sum of ST (j 0 , D̄ ∪ {j}) and the value on entry indexed
(J \ {j}, j 0 , D00 \ D̄). The resulting cost of the (4-a) move is then found in the
19

entry indexed by (F 0 ∪ B 0 , b, D0 ).
It is straightforward to show that the above described dynamic programming computes the cost of the move as desired. The only difference for type
(4-b) moves is that J is a subset of F 0 ∪ B 0 ∪ {v}. The table has at most
0
0
0
0
2|F ∪B ∪{v}|−1+|D | entries, we check at most (|F 0 ∪ B 0 ∪ {v}| − 1) · 2D combinations of j 0 and D̄, and for each of them call the Nederlof’s algorithm in
O(2|D̄| · nO(1) ) time. This gives O(22q+3|T | · nO(1) ) time to compute the cost of
the move. In fact, taking the table for F 0 = F , B 0 = B, and D0 = D one can
determine the cost of each possible (4-a) move from the configuration (F, B, D)
by simply looking to the appropriate entry of the table. This can be done similarly for (4-b) moves and each v. Therefore, computing the costs of all type (4)
moves takes O(22q+4|T | · n2q+O(1) ) time in total.
Finally, there are at most 2|T | moves of type (5), and computing the cost of
each of them amounts to single run of the Nederlof’s algorithm, thus in total
taking O(22|T | · nO(1) ) time.
The game graph has in total O(n2q−1 · m · 2|T | + n2q−1 · m · 3|T | + n2q+1 ·
2|T | 2q
2
2 + 2|T | ) = O(n2q+1 · 22|T |+2q ) arcs. Hence, the Dijkstra’s algorithm [8]
using the Fibonacci heaps [13], with running time O(|V 0 | log |V 0 | + |A0 |) runs in
O(n2q · 2|T | · log(n2q · 2|T | ) + n2q+1 · 22|T |+2q ) = O(n2q+1 · 22|T |+2q ) time.
To sum up, the running time of the algorithm is determined by the computation of the costs of type (4) moves, which takes O(22q+4|T | · n2q+O(1) ) time.
In fact the constants in the above running time can be slightly reduced by
storing some values of ST () and by a more detailed analysis which we ommit
here.

4

Restriction to Solutions with Trunk

In this section we relax the conditions on the solutions of the problem, namely,
we consider the following problem:
q-Root Steiner Tree with Trunk (q-RST-T)
Input: A directed graph G = (V, A), two subsets of its vertices R, T ⊆ V
with |R| = q.
We
Task: Find a minimum size of a set S ⊆ V such that in G[R ∪ S ∪ T ] there
is a vertex v, a directed path from r to v for every r ∈ R, and a directed
path from v to t for every t ∈ T .
show that this problem can be solved in similar time as q-RST-P.
Theorem 3. For every q ≥ 1 the problem q-RST-T is fixed-parameter tractable
with respect to T . Namely, there is an algorithm solving it in O(22q+4|T | ·
n3q+O(1) ) time.
Proof. We reduce the problem to the previous one in the following way. Suppose
there was a solution S to the problem and v was the vertex with the specified
properties. For each vertex r in R we can identify the first vertex r0 on a path
from r to v in G[R ∪ S ∪ T ] that is reachable from v in the same graph. Let us
20

denote R0 the set of all such r0 ’s. Then, the solution can be divided into parts
providing paths from R to R0 and to a q-RST-P instance (G, R0 , T \ R0 ).
To apply the above idea, the algorithm first guesses a mapping φ : R → V ,
i.e., tries all possible such mappings. For each of them let us denote R0 = φ(R).
Now for each φ we compute the minimum size of a solution for the |R0 |-RST-P
0
0
instance
). We increase this value by |R0 \ (R ∪ T )| and by the
P (G, R , T \0 R −1
sum r0 ∈R0 ST R(r , φ (r0 )), where ST R(x, Y ) is a minimum size of a vertex
set S such that in G[{x} ∪ S ∪ Y ] there is a path from each vertex of Y to x,
i.e., a variant of directed Steiner in-tree. We output the minimum of the values
obtained this way over all φ’s.
To see that this algorithm correctly computes the minimum size of a set
S ⊆ V such that in G[R ∪ S ∪ T ] there is a vertex v, a directed path from r to
v for every r ∈ R, and a directed path from v to t for every t ∈ T , let us first
show that the value computed by the algorithm is at least the optimal value for
the instance. To this end, it is enough to observe that for each φ the Steiner
in-trees computed in the sum together with the set R0 provide a path from r to
φ(r) for each r ∈ R. Moreover, the solution to the instance |R0 |-RST-P instance
(G, R0 , T \ R0 ) provides paths from r0 to t for each r0 ∈ R0 and each t ∈ T ∪ R0 .
Therefore, denoting v = r0 for any r0 ∈ R0 , these sets together provide a solution
for the q-RST-T instance and the optimal value for the instance must be at most
the one computed by the algorithm.
For the other direction, let us now repeat more formally the idea from the
beginning of the proof. Suppose S ⊆ V is a set of minimum size such that in
G[R ∪ S ∪ T ] there is a vertex v, a directed path from r to v for every r ∈ R,
and a directed path from v to t for every t ∈ T . Let H be the subgraph of
G[R ∪ S ∪ T ] with the minimum number of arcs such that in H there is still a
directed path from r to v for every r ∈ R, and a directed path from v to t for
every t ∈ T . Now for each r ∈ R let us denote φ(r) the first vertex on some
path from r to v in H reachable from v in H and denote R0 = φ(R).
For each r0 ∈ R0 denote Xr0 the set of vertices on the paths in H from
the vertices
in φ−1 (r0 ) to r0 , except for the vertices in φ−1 (r0 ) and r0 itself and
S
X = r0 ∈R0 Xr0 . We let Y = S \ (R0 ∪ X). We would like to show that the sets
Xr0 ∪ φ−1 (r0 ) ∪ {r0 } are disjoint for distinct r0 ’s and that H[R0 ∪ Y ∪ T ] contains
a path from each vertex r0 ∈ R0 to each vertex t ∈ R0 ∪ T .
If there were x, y ∈ R0 , x 6= y and a vertex a ∈ (Xx ∪φ−1 (x))∩(Xy ∪φ−1 (y)),
then there are two paths from a to v in H, one through x and one through y,
and we can omit the first arc from one of these paths from H to obtain a graph
in which there is a directed path from r to v for every r ∈ R, and a directed
path from v to t for every t ∈ T (note that the arc cannot be part of any path
in H starting in v, since it is not reachable from v in H). This would contradict
the minimality of H. If x ∈ (Xy ∪ φ−1 (y)), then there must be an r ∈ φ−1 (y)
such that x is on the path from r to y contradicting the choice of y as φ(r) and
similarly if y ∈ (Xx ∪ φ−1 (x)). Hence, the sets are indeed disjoint.
Now let us show that H[R0 ∪ Y ∪ T ] contains a path from each vertex r0 ∈ R0
to each vertex t ∈ R0 ∪ T . Note that no vertex in (R ∪ S ∪ T ) \ (R0 ∪ Y ∪ T ) =
(X ∪ R) \ R0 is reachable from v in H by the definition of φ (and R0 ). Each
21

vertex r0 ∈ (R0 ∪ T ) is reachable from v in H. Since φ(r) is a vertex on a path
from r to v in H, there is a path from r0 to v in H for every r0 ∈ R0 . Since all
the vertices on these paths are reachable from v, they are not in (X ∪ R) \ R0
and the paths are preserved in H[R0 ∪ Y ∪ T ]. It follows that H[R0 ∪ Y ∪ T ] has
the desired property.
We know that {Xr0 | r0 ∈ R0 } ∪ {R0 \ (R ∪ T ), Y } is a partition of S. We also
know that |Xr0 | is an upper bound for ST R(r0 , φ−1 (r0 )) for each r0 ∈ R0 and
that |Y | is an upper bound for the minimum size of a solution for the |R0 |-RSTP instance (G, R0 , T \ R0 ). It follows that the value computed by the algorithm
is at most the optimal value for the instance, finishing the proof of correctness.
For the running time, there are nq possible φ’s and for each of them we
need to solve a q 0 -RST-P instance for some q 0 ≤ q which takes O(22q+4|T | ·
n2q+O(1) ) time and compute q 0 values of ST R(). This can be again done using
the Nederlof’s algorithm (on the reversed digraph), each of the computations
taking O(2q · nO(1) ) time. Hence, in total, the algorithm runs in O(22q+4|T | ·
n3q+O(1) ) time.
Suppose now that we restrict to solutions such that there is a vertex v that
is an all but a constant number h of the required paths. More formally, for all
but h (given) pairs (r, t) ∈ R × T the solution contains a path from r to v and at
the same time a path from v to t. To solve such a variant it is enough to replace
the collection of Steiner in-trees used in the proof of Theorem 3 by a solution
to a DSN instance, where the set of required pairs is formed by the paths not
going over v and the paths from r to φ(r) for each r. Therefore, using the DSN
algorithm of Feldman and Ruhl, we can solve also this variant of the problem
in O(2O(q+|T |) · nO(q+h) ) time.

5

Planar Graphs

In this section we show how to modify the method of Chitnis et al. [5] for SCSS
in planar graphs (and graphs excluding a fixed minor) to show the following
result.
Theorem 4. q-Root Steiner Tree with Pedestal in planar graphs √and
graphs excluding a fixed minor can be solved in O(2O(q log q+|T | log q) · nO( q) )
time.
The rest of the section is devoted to the proof of this theorem. Our goal is
to apply the framework of Chitnis et al. to our accelerated game instead of the
original game of Feldman and Ruhl.
The main idea of Chitnis et al. is to introduce supermoves (for more details see Sections 3 and 4 of [5]) and then show that there is an optimal move
sequence of the original game which can be partitioned into O(q) such supermoves. Moreover, there are only O(q) vertices describing the endpoints of the
moves. The algorithm then guesses the sequence of the supermoves, without
guessing the actual endpoints of the moves, but merely which endpoints are the
same (Subsection 5.1 of [5]).
22

Based on the guess, the algorithm constructs a special directed graph D
with vertices being the endpoints of the moves and an extra vertex per each
supermove of one of the types. Chitnis et al. then show that the underlying
undirected graph of D must be a minor of the underlying undirected graph
of the input digraph, or the sequence of supermoves cannot be realized in the
input digraph. It follows that D is planar and, as it has O(q) vertices, the
√
treewidth of its underlying undirected graph is O( q) [7]. The treewidth of
√
the constructed digraph is checked in 2O( q) · k time by the 5-approximation
algorithm of Bodlaender et al. [3]. If the treewidth is too large, the guess is
discarded (Subsection 5.2 of [5]).
Now they take a universe U = V ∪ V 4 and construct two functions cv :
V (D) × U → Z+ ∪ {∞} and ce : V (D)2 × U 2 → Z+ ∪ {∞} which describe the
costs of mapping the endpoints of particular supermove represented by a vertex
or an arc in D to particular vertices in the input digraph.
P Due to Klein and
Marx [23], a mapping φ : V (D) → U minimizing Bφ = v∈V (D) cv(v, φ(v)) +
√
P
O(tw(D))
= nO( q) time. The
{u,v}∈E(D) ce(u, v, φ(u), φ(v)) can be found in |U |
minimum value of such Bφ over all valid guesses of the algorithm then gives the
cost of the optimal solution to the instance (Section 6 of [5]).
There are three differences between the original game of Feldman and Ruhl
and our accelerated game:
(i) moves of our game also manipulate the D-tokens;
(ii) there is no analogue of the move of type (4-b) in the original game; and
(iii) there is no move of type (5) in the original game.
The point (iii) is the easiest to solve. Since such a move can be only used at
the end of the move sequence, we split the sequence to this move and the rest.
We search for the rest of the sequence using the framework by Chitnis et al.
and increase the final value by the cost of the type (5) move. In yet another
words, we guess the D-tokens processed by the move of type (5), remove the
corresponding vertices from T and add the cost of the move to the final value.
To solve point (i) we observe that the manipulated D-tokens can be seen as
an additional label on the move that influences its cost, but does not change its
type. When grouping the moves into supermoves, the set of D-tokens processed
by a supermove is just the union of the sets of D-tokens processed by the
individual moves.
c
Finally let us focus on the point (ii). Let (F, B, D) →
− ((F \ F 0 ) ∪ {v}, (B \
B 0 ) ∪ {f }, D \ (D0 ∪ {f })), be some move of type (4-b). There is an F -token
moved from f to v over some path P and a B-token moved from some point b
on path P to f . Let us suppose that b is the furthest from f among the vertices
from B 0 on P . Ignoring for the moment the D-tokens, we could split the move
into two parts, the first one being a type (4-a) move between f and b and the
other being sequence of (3-a) moves moving the F -token from b to v.
However, there might be also some D-tokens picked up on the part of the
path P between b and v. For that reason we now have to allow the (3-a) moves
23

to also pick up D-tokens (as (3-b) and (4-a) do). Nevertheless, for a type (3-a)
move to be able to pick up D-tokens, we must be sure that the involved F -token
already took part in at least one flip, i.e., move of type (4-a). We call such F tokens active. Then the D-tokens processed in the (3-a) move can take the path
traversed by the F -token since the flip in reverse direction to merge with the
B-token involved in the flip. This condition on the F -token being active would
complicate the description of the game, since we would have to keep track of
the F -tokens that are active. However, it is easy to check this condition on
the description of the sequence of supermoves as guessed in the Chitnis et al.
framework.
Hence, we can use just the moves (3-a), (3-b), and (4-a), where each of them
can be equipped with a set of D-tokens to be processed within the move. These
naturally correspond to single forward, single backward, and flipping moves of
the Feldman and Ruhl game.
We classify the moves the same way as Chitnis et al. into EmptyFlip,
NonEmptyFlip, SingleForward, SingleForwardMeet, etc., with one additional
parameter being the set of D-tokens processed. Note specifically, we call a flip
empty even if it processes some D-tokens. We define the supermoves Alone, Absorb, AbsorbAndMeet, Meet, NonEmptyFlip, and MultipleFlip and the cleanness of MultipleFlip exactly the same way as Chitnis et al., again equipping
each supermove with the set of the processed D-tokens. Now since the set of
moves we have is the same as the one of Feldman and Ruhl, the Theorem 5.1 of
[5] applies to our game. That is, there is an optimal sequence of moves for our
game that can be partitioned into O(q) supermoves such that each MultipleFlip
is clean. Moreover the sets of internal vertices of any two supermoves of this
sequence have empty intersection (see Lemma 5.1 of [5]).
By Lemma 5.2 of [5], there are 2O(q log q) unlabeled descriptions for the Feldman and Ruhl game, that is sequences of O(q) supermoves with variables instead
of the endpoints. In our case we further describe in which supermove we process
which D-tokens. Since there are O(q) supermoves and at most |T | D-tokens,
there are (O(q))|T | = 2O(|T | log q) possible assignments of the D-tokens to the
supermoves. Hence, we have 2O(q log q+|T | log q) unlabeled descriptions for our
game in total.
We call an unlabeled description valid if it satisfies all the conditions of
Definition 5.1 of [5] and moreover, for each forward supermove equipped with
a non-empty set of D-tokens, the involved F -token is also involved in a flip
supermove prior to this supermove. As in Chitnis et al., the validity of an
unlabeled description can be checked in O(q) time.
We associate with a valid unlabeled description X the directed graph DX
exactly the same way Chitnis et al. do. By Theorem 5.2 of [5], if the unlabeled description X ∗ is constructed from the optimal sequence of moves given
above, then the underlying undirected graph of DX ∗ is a minor of the underlying
undirected graph of the input digraph G. Since DX has O(q) vertices, due to
Demaine and Hajiaghayi [7], the treewidth of the underlying undirected graph
√
of DX ∗ is O( q). We can check for each valid unlabeled description X whether

24

√
√
the treewidth of the underlying undirected graph of DX is O( q) in 2O( q) · q
time using the 5-approximation algorithm of Bodlaender et al. [3].
Before we start guessing the labeling for the unlabeled description, we further
guess for each D-token processed in a NonEmptyFlip, in which part of the
sequence α → γ1 → γ2 · · · → γ` → α0 it is processed. Since there are O(q)
possibilities for each of the at most |T | tokens, there are 2O(|T | log q) possibilities
in total. We label each edge added to the DX for the NonEmptyFlip with the
set of D-tokens processed in that part of the sequence. If we added a new
vertex to DX for a MultipleFlip, then we label it with the the set of D-tokens
processed in it, otherwise we label the edge added for that move. For all the
other supermoves we label the edge added to DX for the supermove with the
the set of D-tokens processed in it.
Before we introduce the functions ce and cv, let us show how to compute a
cost of a MultipleFlip(f, b, u, v, u0 , v 0 , D0 ), where D0 is a set of D-tokens to be
processed in it. We show that it can be computed similarly to the optimum
value of 2-RST-P instance. We construct the game graph of the accelerated
game for the 2-RST-P instance (G, {u, v}, D0 ). Observe that if the two tokens
in this game are f and b, then all the allowed moves in this accelerated game are
(after the decomposition of the (4-b) moves) valid parts of a MultipleFlip. Since
both ({u}, {v}, D0 ) and ({u0 }, {v 0 }, ∅) are valid configurations of this game, we
can compute the cost of the supermove as the length of a shortest path between
the two configurations. This takes O(24|T | · nO(1) ) time (see Subsection 3.3).
Now we are ready to define the cost functions ce and cv over the universe
U = V ∪ V 4 . We define the function cv exactly the same way as Chitnis et
al., taking the appropriate cost of the MultipleFlip with the set D0 of processed
D-tokens as assigned to the node of DX where relevant. For ce we also take
the new cost of MultipleFlip where relevant. Additionally, in the case where
Chitnis et al. compute ce(α, α0 , v, w) from the length of a shortest path from
vertex v to vertex w in G for some edge (α, α0 ) of DX equipped with set D0
we replace the formula by ce(α, α0 , v, w) = ST (v, {w} ∪ D0 ) · cv(α, v) · cv(α0 , w),
where ST (x, Y ) is as defined in Subsection 3.2.
Now by result of Klein
P and Marx [23] wePcan find a mapping φ : V (D) →
U minimizing Bφ =
v∈V (D) cv(v, φ(v)) +
{u,v}∈E(D) ce(u, v, φ(u), φ(v)) in
√
|U |O(tw(D)) = nO( q) time.
Our algorithm guesses all possible unlabeled descriptions of appropriate
length and for each of them checks its validity. For the valid ones it constructs
the directed graph DX and checks the treewidth of its underlying undirected
graph. If it is too large, the guess is discarded, otherwise we further guess the
distribution of the D-tokens among the NonEmptyFlips. Then we compute the
functions cv and ce and find the φ minimizing the Bφ . We output the minimum
over all Bφ ’s obtained this way.
Since there are 2O(q log q+|T | log q) unlabeled descriptions and 2O(|T | log q) distributions of the D-tokens, there are 2O(q log q+|T | log q) possible different guesses
in total. Checking validity and
constructing the digraph takes linear time, check√
ing the treewidth takes 2O( q) time. There are O(n4 ) vertices in the universe

25

U and O(n8 ) their pairs. For each of them, the computation of cv or ce, respectively, takes at most O(24|T | · nO(1)
) time. Finally, the execution of the
√
O( q)
algorithm of Klein and Marx
takes
n
time. Therefore, the algorithm runs
√
in 2O(q log q+|T | log q) · nO( q) time in total.
The correctness follows from the representability of the accelerated game
and from Lemmata 6.2 and 6.3 of [5]. This finishes the proof of the theorem.

6

Conclusion and Future Directions

We have shown that there is a nice special case of DSN that allows for as
effective algorithms as were known for DST and SCSS, even with respect to
planar graphs. We characterized that the crucial property of the solution to
allow this is the existence of a vertex over which almost all paths required by
the problem definition “factorize”. An interesting open question is what is the
complexity of q-RST (the unrestricted variant) in planar graphs.
Another interesting question is tied to the other parameterization of the
problems. We are not aware of any result determining the complexity of SCSS in
planar graphs with respect to the parameterization the number of nonterminals
in the solution.

References
[1] Berman, P., Bhattacharyya, A., Makarychev, K., Raskhodnikova, S.,
Yaroslavtsev, G.: Approximation algorithms for spanner problems and directed Steiner forest. Information and Computation 222, 93 – 107 (2013)
[2] Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets Möbius:
fast subset convolution. In: STOC 2007. pp. 67–74. ACM (2007)
[3] Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov,
D., Pilipczuk, M.: An o(ck n) 5-approximation algorithm for treewidth. In:
FOCS 2013. pp. 499–508 (2013)
[4] Charikar, M., Chekuri, C., Cheung, T.Y., Dai, Z., Goel, A., Guha, S., Li,
M.: Approximation algorithms for directed Steiner problems. Journal of
Algorithms 33(1), 73–91 (1999)
[5] Chitnis, R., Hajiaghayi, M., Marx, D.: Tight bounds for planar strongly
connected Steiner subgraph with fixed number of terminals (and extensions). In: SODA 2014. pp. 1782–1801. SIAM (2014)
[6] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk,
M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)
[7] Demaine, E.D., Hajiaghayi, M.: Graphs excluding a fixed minor have
grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. In: SODA 2005. pp. 682–689. SIAM (2005)
26

[8] Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1(1), 269–271 (1959)
[9] Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity.
Texts in Computer Science, Springer (2013)
[10] Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1,
195–207 (1972)
[11] Erickson, R.E., Monma, C.L., Veinott, Jr., A.F.: Send-and-split method for
minimum-concave-cost network flows. Mathematics of Operations Research
12(4), 634–664 (1987)
[12] Feldman, J., Ruhl, M.: The directed Steiner network problem is tractable
for a constant number of terminals. SIAM Journal on Computing 36(2),
543–561 (2006)
[13] Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved
network optimization algorithms. J. ACM 34(3), 596–615 (1987)
[14] Fuchs, B., Kern, W., Mölle, D., Richter, S., Rossmanith, P., Wang, X.:
Dynamic programming for minimum Steiner trees. Theory of Computing
Systems 41(3), 493–500 (2007)
[15] Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NPcomplete. SIAM J. Appl. Math. 32(4), 826–834 (1977)
[16] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the
Theory of NP-Completeness. Freeman (1979)
[17] Guo, J., Niedermeier, R., Suchý, O.: Parameterized complexity of arcweighted directed Steiner problems. SIAM J. Discrete Math. 25(2), 583–599
(2011)
[18] Hakimi, S.L.: Steiner’s problem in graphs and its implications. Networks
1, 113–133 (1971)
[19] Halperin, E., Kortsarz, G., Krauthgamer, R., Srinivasan, A., Wang, N.:
Integrality ratio for group Steiner trees and directed Steiner trees. SIAM
J. Comput. 36(5), 1494–1511 (2007)
[20] Held, M., Karp, R.M.: A dynamic programming approach to sequencing
problems. Journal of SIAM 10, 196–210 (1962)
[21] Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst.
Sci. 62(2), 367–375 (2001)
[22] Jones, M., Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Suchý, O.:
Parameterized complexity of directed Steiner tree on sparse graphs. In:
ESA 2013. LNCS, vol. 8125, pp. 671–682. Springer (2013)

27

[23] Klein, P.N., Marx, D.: Solving planar k-terminal cut in o(nc
ICALP 2012. LNCS, vol. 7391, pp. 569–580. Springer (2012)

√
k

) time. In:

[24] Kortsarz, G., Nutov, Z.: Approximating minimum cost connectivity problems. In: Handbook of Approximation Algorithms and Metaheuristics,
chap. 58. CRC (2007)
[25] Levin, A.Y.: Algorithm for the shortest connection of a group of graph
vertices. Sov. Math. Dokl. 12, 1477–1481 (1971)
[26] Marx, D.: Can you beat treewidth? Theory of Computing 6(1), 85–112
(2010)
[27] Misra, N., Philip, G., Raman, V., Saurabh, S., Sikdar, S.: FPT algorithms
for connected feedback vertex set. J. Comb. Optim. 24(2), 131–146 (2012)
[28] Nederlof, J.: Fast polynomial-space algorithms using inclusion-exclusion.
Algorithmica 65(4), 868–884 (2013)
[29] Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems.
Journal of Computer and System Sciences 67(4), 757 – 771 (2003)

28

