Steiner Network Problems on Temporal Graphs∗
Alex Khodaverdian1 , Benjamin Weitz2 , Jimmy Wu3 , and Nir Yosef4
1

UC Berkeley, Berkeley, USA
alexkhodaverdian@berkeley.edu
UC Berkeley, Berkeley, USA
bsweitz@cs.berkeley.edu
Stanford University, Stanford, CA, USA
jimmyjwu@stanford.edu
UC Berkeley, Berkeley, USA
niryosef@eecs.berkeley.edu

2
3

arXiv:1609.04918v2 [cs.CC] 1 Sep 2017

4

Abstract
We introduce a temporal Steiner network problem in which a graph, as well as changes to its
edges and/or vertices over a set of discrete times, are given as input; the goal is to find a minimal
subgraph satisfying a set of k time-sensitive connectivity demands. We show that this problem,
k-Temporal Steiner Network (k-TSN), is NP-hard to approximate to a factor of k − , for every
fixed k ≥ 2 and  > 0. This bound is tight, as certified by a trivial approximation algorithm.
Conceptually this demonstrates, in contrast to known results for traditional Steiner problems,
that a time dimension adds considerable complexity even when the problem is offline.
We also discuss special cases of k-TSN in which the graph changes satisfy a monotonicity
property. We show approximation-preserving reductions from monotonic k-TSN to well-studied
problems such as Priority Steiner Tree and Directed Steiner Tree, implying improved approximation algorithms.
Lastly, k-TSN and its variants arise naturally in computational biology; to facilitate such
applications, we devise an integer linear program for k-TSN based on network flows.
1998 ACM Subject Classification F.2 Analysis of Algorithms and Problem Complexity
Keywords and phrases Steiner tree, temporal graphs, hardness of approximation, approximation
algorithms, network biology
Digital Object Identifier 10.4230/LIPIcs.CVIT.2016.23

1

Introduction

The Steiner Tree problem, along with its many variants and generalizations, is a core family
of NP-hard combinatorial optimization problems. Like many such problems, they have been
intensely studied in both the classic “static” setting in which a single graph is given as input
up-front, as well as the online and dynamic settings, in which an algorithm is required to
produce outputs or decisions as parts of the input arrive. In this paper, we offer a perspective
that sits in between the static and the online cases; in our temporal setting, a graph, as well
as changes to it over a set of discrete times, are all given as immediate input. Our study of
this problem draws motivation and techniques from several lines of research, which we briefly
summarize.
∗

This work was partially supported by the National Science Foundation Graduate Research Fellowship
Program award DGE 1106400, NIH grants U01HG007910 and U01MH105979, and the U.S.-Israel
Binational Science Foundation.

© Alex Khodaverdian, Benjamin Weitz, Jimmy Wu, and Nir Yosef;
licensed under Creative Commons License CC-BY
42nd Conference on Very Important Topics (CVIT 2016).
Editors: John Q. Open and Joan R. Acces; Article No. 23; pp. 23:1–23:18
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

23:2

Steiner Network Problems on Temporal Graphs

Classic Steiner problems The most basic Steiner problem is Steiner Tree: given a weighted
undirected graph G = (V, E) and a set of terminals T ⊆ V , find a minimum-weight subtree
that spans T . The Steiner Forest problem generalizes this: given G = (V, E) and a set of
demand pairs D ⊆ V × V , find a subgraph that connects each pair in D. Currently the
best known approximation algorithms give a ratio of 1.39 for Steiner Tree [5] and 2 for
Steiner Forest [1]. These problems are known to be NP-hard to approximate to within some
small constant [10].
For directed graphs, we have the Directed Steiner Network problem (DSN), in which we are
given a weighted directed graph G = (V, E) and k demands (a1 , b1 ), . . . , (ak , bk ) ∈ V × V , and
must find a minimum-weight subgraph in which each ai has a path to bi . When k is fixed, DSN
admits a polynomial-time exact algorithm [14]. For general k, the best known approximation
algorithms have ratio O(k 1/2+ ) for any fixed  > 0 [15, 9]. On the complexity side, Dodis
1−
and Khanna [12] ruled out a polynomial-time O(2log n )-approximation unless NP has
quasipolynomial-time algorithms. An important special case of DSN is Directed Steiner Tree,
in which all demands have the form (r, bi ) for some root node r. This problem has a
O(k  )-approximation scheme [6] and a lower bound of Ω(log2− n) [16].
Another related problem which will be useful to us is Priority Steiner Tree, in which each
edge has an associated priority value, and each demand must be routed using edges of at
least a certain priority. Charikar, Naor, and Schieber introduced this problem and gave a
O(log k)-approximation [7].
Network Biology A central object of study in molecular biology is a protein-protein interaction (PPI) network, in which nodes represent proteins and each edge (u, v) represents a
physical interaction between proteins u and v, occurring with some probability p(u, v). Thus
by a chain of such interactions, a signal can be propagated through the network from one
protein a to another protein b with which it has no direct contact.
A common setting is that from laboratory experiments, it is known that when a particular
biological process occurs, for a certain collection of protein pairs {(a1 , b1 ), . . . , (ak , bk )}, there
must be a chain of interactions between each ai and bi , though it is not known which
intermediate proteins participated in these interaction chains. To infer these intermediate
proteins computationally, we can try to find a subgraph, of maximum joint probability, that
simultaneously enables signals between all the protein pairs, thereby explaining the overall
biological activity. Setting the edges to have weights w(e) = − log p(e), the task becomes
minimizing the total edge weight—precisely the Steiner Forest problem. Indeed, variations
on this idea have been used effectively by [23], [18], [25], [4], [24], and others to understand
signal transduction pathways in living cells.
Despite these successes, most of the existing literature ignores a critical dimension of
the problem: in reality, proteins can become activated or inactivated over time, forming a
dynamic PPI network [21]. An important research direction is therefore to study Steiner
problems that incorporate the times at which each demand should be satisfied; the work
presented here is motivated by this challenge. See Appendix E for more details.
In this paper, we introduce temporal generalizations of Directed Steiner Network and
Steiner Forest. The main variant we consider is the following:
k-Temporal Steiner Network (k-TSN)
Input:
1. A sequence of undirected graphs or frames G1 = (V, E1 ), G2 = (V, E2 ), . . . , GT =
S
(V, ET ) on the same vertex set. Each edge e in the underlying edge set E := t Et

A. Khodaverdian, B. Weitz, J. Wu, and N. Yosef

23:3

has weight w(e) ≥ 0.
2. A set of k connectivity demands D ⊆ V × V × [T ].
We call G = (V, E) the underlying graph. We say a subgraph H ⊆ G satisfies demand
(a, b, t) ∈ D iff H contains an a-b path P along which all edges exist in Gt .
Output: A minimum-weight subgraph H ⊆ G that satisfies every demand in D.
Similarly k-Directed Temporal Steiner Network (k-DTSN) is the same problem except that
the edges are directed, and a demand (a, b, t) must be satisfied by a directed path from a to
b in Gt .

1.1

Our Results

In section 3, we show a strong inapproximability result for k-Temporal Steiner Network
(k-TSN) and its directed version k-DTSN:
I Theorem 1.1 (Main Theorem). k-TSN and k-DTSN are NP-hard to approximate to a
factor of k −  for every k ≥ 2 and every constant  > 0. For k-DTSN, this holds even when
the underlying graph is acyclic.
Thus the best approximation ratio one can hope for is k, which is easily achieved by taking
the union of shortest paths for each demand. This contrasts with the static Steiner network
problems, which have nontrivial approximation algorithms and efficient fixed-parameter
algorithms. Our proof is via a reduction from Feige’s k-prover system [13], which can be
viewed as a Label Cover problem on partite hypergraphs.
In section 4, we discuss a broad class of special cases in which the edges are monotonic: once
an edge exists, it exists for all future times. We observe that monotonic k-TSN is essentially
equivalent to the well-studied Priority Steiner Tree problem, and inherits the approximability
bounds for that problem.
I Theorem 1.2. Monotonic k-TSN has a polynomial-time O(log k)-approximation algorithm.
It has no Ω(log log n)-approximation algorithm unless NP ∈ DTIME(nlog log log n ).
For monotonic k-DTSN with a single source (that is, every demand is of the form (r, b, t)
for a common root node r), we show the following:
I Theorem 1.3. Monotonic Single-Source k-DTSN has a polynomial-time O(k  )-approximation
algorithm for every  > 0. It has no Ω(log2− n)-approximation algorithm unless NP ∈
ZPTIME(npolylog(n) ).
This is achieved via approximation-preserving reductions to and from Directed Steiner Tree,
which is known to have an O(k  )-approximation scheme [6] and a Ω(log2− n) lower bound [16].
We also devise an explicit approximation algorithm achieving the same upper bound.
Finally for the general k-DTSN problem, we present an integer linear program in Appendix C. We make an implementation of this publicly available at https://github.com/
YosefLab/dynamic_connectivity.

2

Preliminaries

Note that the formulations of k-TSN and k-DTSN in the Introduction involved a fixed
vertex set; only the edges change over the times or frames. It is also natural to formulate
the temporal Steiner network problem with nodes changing over time, or both nodes and
edges. However by the following proposition, it is no loss of generality to discuss only the
edge-temporal variant.

CVIT 2016

23:4

Steiner Network Problems on Temporal Graphs

I Proposition 2.1. The edge, node, and node-and-edge variants of k-TSN are mutually
polynomial-time reducible via strict reductions (i.e. preserving the approximation ratio exactly).
Similarly all three variants of k-DTSN are mutually strictly reducible.
We defer the precise definitions of the other two variants, as well as the proof of this
proposition, to Appendix A.
Next we state the Label Cover problem, which is the starting point of one of our reductions
to k-TSN.
I Definition 2.2 (Label Cover (LC)). An instance of this problem consists of a bipartite
graph G = (U, V, E) and a set of possible labels Σ. The input also includes, for each edge
(u,v)
(u,v)
(u, v) ∈ E, projection functions πu
: Σ → C and πv
: Σ → C, where C is a common
set of colors; Π = {πve : e ∈ E, v ∈ e} is the set of all such functions. A labeling of G is a
function φ : U ∪ V → Σ assigning each node a label. We say a labeling φ satisfies an edge
(u,v)
(u,v)
(u, v) ∈ E, or (u, v) is consistent under φ, iff πu
(φ(u)) = πv
(φ(v)). The task is to find
a labeling that satisfies as many edges as possible.
This slightly generalizes the original definition in [2]. It has the following gap hardness,
which follows by combining the PCP theorem [3] with Raz’s parallel repetition theorem [22].
I Theorem 2.3. For every  > 0, there is a constant |Σ| such that the following promise
problem is NP-hard: Given a Label Cover instance (G, Σ, Π), distinguish between the following
cases:
(YES instance) There exists a total labeling of G; i.e. a labeling that satisfies every edge.
(NO instance) There does not exist a labeling of G that satisfies more than |E| edges.
In section 3, we use Label Cover to show (2 − )-hardness for 2-TSN and 2-DTSN; that is,
when there are only two demands. To prove our main result however, we will actually need a
generalization of Label Cover to partite hypergraphs, called k-Partite Hypergraph Label Cover.
Out of space considerations we defer the statement of this problem and its gap hardness to
Appendix B, where the (2 − )-hardness result is generalized to show (k − )-hardness for
general number of demands k.

3
3.1

Hardness of Temporal Steiner Problems
Overview of the Reduction

We first outline our strategy for reducing Label Cover to the temporal Steiner problems;
specifically, we reduce to 2-TSN. A similar hardness for k-TSN is obtained by using the same
ideas, but reducing from k-Partite Hypergraph Label Cover.
Consider the nodes u1 , . . . , u|U | on the “left” side of the LC instance. We build, for each
ui , a gadget (which is a small subgraph in the Steiner instance) consisting of multiple parallel
directed paths from a source to a sink—one path for each possible label for ui . We then chain
together these gadgets, so that the sink of u1 ’s gadget is the source of u2 ’s gadget, and so
forth. Finally we create a connectivity demand from the source of u1 ’s gadget to the sink of
u|U | ’s gadget, so that a solution to the Steiner instance must have a path from u1 ’s gadget,
through all the other gadgets, and finally ending at u|U | ’s gadget. This path, depending on
which of the parallel paths it takes through each gadget, induces a labeling of the left side of
the LC instance. We build an analogous chain of gadgets for the nodes on the right side of
the LC instance.

A. Khodaverdian, B. Weitz, J. Wu, and N. Yosef

23:5

The last piece of the construction is to ensure that the Steiner instance has a low-cost
solution if and only if the LC instance has a consistent labeling. This is accomplished by
setting all the ui gadgets to exist only at time 1 (i.e. in frame G1 ), setting the vj gadgets to
exist only in G2 , and then merging certain edges from the ui -gadgets with edges from the
vj -gadgets, replacing them with a single, shared edge that exists in both frames. Intuitively,
the edges we merge are from paths that correspond to labels that satisfy the Label Cover
edge constraints. The result is that a YES instance of LC (i.e. one with a total labeling) will
enable a high degree of overlap between paths in the Steiner instance, so that there is a very
low-cost solution. On the other hand, a NO instance of LC will not result in much overlap
between the Steiner gadgets, so every solution will be costly.
Let us define some of the building blocks of the reduction we just sketched:
A bundle is a graph gadget consisting of a source node b1 , sink node b2 , and parallel,
disjoint strands (defined shortly) from b1 to b2 .
A chain of bundles is a sequence of bundles, with the sink of one bundle serving as the
source of another.
A simple strand is a directed path of the form b1 → c1 → c2 → b2 .
In a simple strand, we say that (c1 , c2 ) is the contact edge. Contact edges have weight 1;
all other edges in our construction have zero weight.
More generally, a strand can be made more complicated, by replacing a contact edge
with another bundle (or even a chain of them). In this way, bundles can be nested, as
shown in Figure 1.
We can merge two or more simple strands from different bundles by setting their contact
edges to be the same edge, and making that edge existent at the union of all times when
the original edges existed (Figure 2).

Figure 1 A bundle whose upper
strand is a chain of two bundles; the
lower strand is a simple strand. Contact
edges are orange.

Figure 2 Three bundles (blue, green,
red indicate different times), with one
strand from each merged together.

Before formally giving the reduction, we illustrate a simple example of its construction.
I Example 3.1. Consider a toy Label Cover instance whose bipartite graph is a single edge,
label set is Σ = {1, 2}, and projection functions are shown:
u
πue

: 1 7→ 1
2 7→ 1

e

v
πve : 1 7→ 2
2 7→ 1

Our reduction outputs this corresponding 2-TSN instance:

CVIT 2016

23:6

Steiner Network Problems on Temporal Graphs

nd
ra
-st

1

(u, ∅, v, 1)-path

(u, 1, v, 2)-path

v1S

2-s

tra

v2S

nd
(u, 2, v, 2)-path

nd

tra

1-s
uS1

uS2

2-s

tra

nd

G1 comprises the set of blue edges; G2 is green. The demands are (uS1 , uS2 , 1) and (v1S , v2S , 2).
The gadget for the Label Cover node u (the blue subgraph) consists of two strands, one for
each possible label. In the v-gadget (green subgraph), the strand corresponding to a labeling
of ‘2’ branches further, with one simple strand for each agreeing labeling of u. Finally, strands
(more precisely, their contact edges) whose labels map to the same color are merged.
The input is a YES instance of Label Cover whose optimal labelings (u gets either label
1 or 2, v gets label 2) correspond to 2-TSN solutions of cost 1 (both gadgets traverse the
(u, 1, v, 2)-path, or both traverse the (u, 2, v, 2)-path). If this were a NO instance and edge e
could not be satisfied, then the resulting 2-TSN gadgets would have no overlap.

3.2

Inapproximability for Two Demands

We now formalize the reduction in the case of two demands; later, we extend this to any k.
I Theorem 3.2. 2-TSN and 2-DTSN are NP-hard to approximate to within a factor of 2 − 
for every constant  > 0. For 2-DTSN, this holds even when the underlying graph is acyclic.
Proof. We describe a reduction from Label Cover to 2-DTSN with an acyclic graph. Given
the LC instance (G = (U, V, E), Σ, Π), construct a 2-DTSN instance (G = (G1 , G2 ), along
S
with two connectivity demands) as follows. Create nodes uS1 , . . . , uS|U |+1 and v1S , . . . , v|V
|+1 .
S
S
Let there be a bundle from each ui to ui+1 ; we call this the ui -bundle, since a choice of path
from uSi to uSi+1 in G will indicate a labeling of ui in G.
The ui -bundle has a strand for each possible label ` ∈ Σ. Each of these `-strands consists
of a chain of bundles—one for each edge (ui , v) ∈ E. Finally, each such (ui , v)-bundle has a
(u ,v)
(u ,v)
simple strand for each label r ∈ Σ such that πui i (`) = πv i (r); call this the (ui , `, v, r)path. In other words, there is ultimately a simple strand for each possible labeling of ui ’s
neighbor v such that the two nodes are in agreement under their mutual edge constraint.
If there are no such consistent labels r, then the (ui , v)-bundle consists of just one simple
strand, which is not associated with any r. Note that every minimal uS1 → uS|U |+1 path (that
is, one that proceeds from one bundle to the next) has total weight exactly |E|.
S
Similarly, create a vj -bundle from each vjS to vj+1
, whose r-strands (for r ∈ Σ) are each
a chain of bundles, one for each (u, vj ) ∈ E. Each (u, vj )-bundle has a (u, `, vj , r)-path for
each agreeing labeling ` of the neighbor u, or a simple strand if there are no such labelings.
Set all the edges in the ui -bundles to exist in G1 only. Similarly the vj -bundles exist
solely in G2 . Now, for each (u, `,n
v, r)-path in G
it with o
the (u, `, v, r)-path in G2 , if
1 , merge

it exists. The demands are D =

S
uS1 , uS|U |+1 , 1 , v1S , v|V
|+1 , 2

.

S
S
We now analyze the reduction.
The main

 idea is that any ui → ui+1 path induces a
S
S
labeling of ui ; thus the demand u1 , u|U |+1 , 1 ensures that any 2-DTSN solution indicates a


S
labeling of all of U . Similarly, v1S , v|V
,
2
forces an induced labeling of V . In the case of a
|+1

A. Khodaverdian, B. Weitz, J. Wu, and N. Yosef

23:7

YES instance of Label Cover, these two connectivity demands can be satisfied by taking two
paths with a large amount of overlap, resulting in a low-cost 2-DTSN solution. In contrast
when we start with a NO instance of Label Cover, any two paths we can choose to satisfy the
2-DTSN demands will be almost completely disjoint, resulting in a costly solution. We now
fill in the details.
Suppose the Label Cover instance is a YES instance, so that there exists a labeling `∗u to
(u,v)
(u,v)
each u ∈ U , and rv∗ to each v ∈ V , such that for all edges (u, v) ∈ E, πu (`∗u ) = πv (rv∗ ).
The following is an optimal solution H∗ to the constructed 2-DTSN instance:
To satisfy the demand at time 1, for each u-bundle, take a path through the `∗u -strand.
In particular for each (u, v)-bundle in that strand, traverse the (u, `∗u , v, rv∗ )-path.
To satisfy the demand at time 2, for each v-bundle, take a path through the rv∗ -strand.
In particular for each (u, v)-bundle in that strand, traverse the (u, `∗u , v, rv∗ )-path.
In tallying the total edge cost, H∗ ∩ G1 (i.e. the subgraph at time 1) incurs a cost of |E|, since
one contact edge in G is encountered for each edge in G. H∗ ∩ G2 accounts for no additional
cost, since all contact edges correspond to a label which agrees with some neighbor’s label,
and hence were merged with the agreeing contact edge in H∗ ∩ G1 . Clearly a solution of cost
S
|E| is the best possible, since every uS1 → uS|U |+1 path in G1 (and every v1S → v|V
|+1 path in
G2 ) contains at least |E| contact edges.
Conversely suppose we started with a NO instance of Label Cover, so that for any
labeling `∗u to u and rv∗ to v, for at least (1 − )|E| of the edges (u, v) ∈ E, we have
(u,v)
(u,v)
πu (`∗u ) 6= πv (rv∗ ). By definition, any solution to the constructed 2-DTSN instance
S
contains a simple uS1 → uS|U |+1 path P1 ∈ G1 and a simple v1S → v|V
|+1 path P2 ∈ G2 . P1
alone incurs a cost of exactly |E|, since one contact edge in G is traversed for each edge in G.
However, P1 and P2 share at most |E| contact edges (otherwise, by the merging process, this
implies that more than |E| edges could be consistently labeled, which is a contradiction).
Thus the solution has a total cost of at least (2 − )|E|.
The directed temporal graph we constructed is acyclic, as every edge points “to the
right” as in Example 3.1. It follows from the gap between the YES and NO cases that
2-DTSN is NP-hard to approximate to within a factor of 2 −  for every  > 0, even on
DAGs. Finally, note that the same analysis holds for 2-TSN, by simply making every edge
undirected; however in this case the graph is clearly not acyclic.
J

3.3

Inapproximability for General k

I Theorem 1.1 (Main Theorem). k-TSN and k-DTSN are NP-hard to approximate to a
factor of k −  for every k ≥ 2 and every constant  > 0. For k-DTSN, this holds even when
the underlying graph is acyclic.
Proof. We perform a reduction from k-Partite Hypergraph Label Cover, a generalization of
Label Cover to hypergraphs, to k-TSN, or k-DTSN with an acyclic graph. Using the same
ideas as in the k = 2 case, we design k demands composed of parallel paths corresponding
to labelings, and merge edges so that a good global labeling corresponds to lots of overlaps
between those paths. The full proof is left to Appendix B.
J
S
Note that a k-approximation algorithm is to simply choose H = t P̃t , where P̃t is the
shortest at → bt path in Gt . Thus by Theorem 1.1, essentially no better approximation is possible in terms of k alone. In contrast, most classic Steiner problems have good approximation
algorithms, or are even exactly solvable for constant k.

CVIT 2016

23:8

Steiner Network Problems on Temporal Graphs

4

Monotonic Special Cases

In light of the tight lower bound, in this section we consider more tractable special cases of the
temporal Steiner problems. Perhaps the simplest scenario in which an o(k)-approximation is
possible is when T  k, in which case we can approximate individual static Steiner instances
using the best known algorithms and combine them. A more interesting and quite natural
restriction is that the changes over time are monotonic:
I Definition 4.1 (Monotonic k-TSN and k-DTSN). In this special case of k-TSN or k-DTSN,
we have that for each e ∈ E and t ∈ [T ], if e ∈ Gt , then e ∈ Gt0 for all t0 ≥ t.
This is a natural extension of k-DTSN based on our motivation from network biology.
Oftentimes, once a protein (node) becomes active, it remains active for the remainder of the
time span being considered. As the node and edge variants are equivalent (Proposition 2.1),
these monotonic cases are good models for known biological observations.
Note also that this notion of monotonicity is analogous to the incremental model often
studied in online algorithms, in which graph elements can be added but not deleted (it is
also analogous to the decremental model, since we can reverse the order of the frames). We
now examine its effect on the complexity of the temporal Steiner problems.

4.1

Monotonicity in the Undirected Case

In the undirected case, monotonicity has a simple effect: it makes k-TSN equivalent to the
following well-studied problem:
I Definition 4.2 (Priority Steiner Tree [7]). The input is a weighted undirected multigraph
G = (V, E, w), a priority level p(e) for each e ∈ E, and a set of k demands (ai , bi ), each with
priority p(ai , bi ). The output is a minimum-weight forest F ⊆ G that contains, between each
ai and bi , a path in which every edge e has priority p(e) ≤ p(ai , bi ).
I Lemma 4.3. Priority Steiner Tree and Monotonic k-TSN have the same approximability.
Proof. We transform an instance of Priority Steiner Tree into an instance of Monotonic k-TSN
as follows: the set of priorities becomes the set of times; if an edge e has priority p(e), it
now exists at all times t ≥ p(e); if a demand (ai , bi ) has priority p(ai , bi ), it now becomes
(ai , bi , p(ai , bi )). If there are parallel multiedges, break up each such edge into two edges
of half the original weight, joined by a new node. Given a solution H ⊆ G to this k-TSN
instance, contracting any edges that were originally multiedges gives a Priority Steiner Tree
solution of the same cost. This reduction also works in the opposite direction (in this case
there are no multiedges), which shows the equivalence.
J
Priority Steiner Tree is known to have a O(log k)-approximation algorithm [7], as well as
a lower bound of Ω(log log n) assuming NP ∈
/ DTIME(nlog log log n ) [11]. This combined with
Lemma 4.3 proves Theorem 1.2.

4.2

Monotonicity in the Directed Case

Now we consider the directed case, and in particular the special case in which all demands
originate from a common source:
I Definition 4.4 (Single-Source Monotonic k-DTSN). This problem is a special case of
Monotonic k-DTSN in which the demands are precisely (a, b1 , t1 ), (a, b2 , t2 ), . . . , (a, bk , tk ), for
some root a ∈ V . We can assume w.l.o.g. that t1 ≤ t2 ≤ · · · ≤ tk .

A. Khodaverdian, B. Weitz, J. Wu, and N. Yosef

23:9

Our goal in this subsection is to show that in terms of approximability, this problem
is equivalent to Directed Steiner Tree (DST), and hence the known bounds for DST apply.
Note that one side of the equivalence is immediate, as Single-Source Monotonic k-DTSN is a
generalization of DST and therefore no easier to approximate.
I Lemma 4.5. Monotonic Single-Source k-DTSN and Directed Steiner Tree have the same
approximability.
For the remainder of this section, we refer to Monotonic Single-Source k-DTSN as simply
k-DTSN. To prove Lemma 4.5, it remains to give an approximation-preserving reduction
from k-DTSN to DST.
The reduction Given a k-DTSN instance (G1 = (V, E1 ), G2 = (V, E2 ), . . . , GT = (V, ET ), D)
with underlying graph G = (V, E), we construct a DST instance (G0 = (V 0 , E 0 ), D0 ) as follows:
G0 contains a vertex v i for each v ∈ V and each i ∈ [k]. It contains an edge (ui , v i ) with
weight w(u, v) for each (u, v) ∈ Ei . Additionally, it contains a zero-weight edge (v i , v i+1 )
for each v ∈ V and each i ∈ [k].
D0 contains a demand (a1 , btii ) for each (a, bi , ti ) ∈ D.
Now consider the DST instance (G0 , D0 ).
I Lemma 4.6. If the k-DTSN instance (G1 , . . . , GT , D) has a solution of cost C, then the
constructed DST instance (G0 , D0 ) has a solution of cost at most C.
Proof. Let H ⊆ G be a k-DTSN solution having cost C. For any edge (u, v) ∈ E(H), define
the earliest necessary time of (u, v) to be the minimum ti such that removing (u, v) would
cause H not to satisfy demand (a, bi , ti ).
I Claim 4.7. There exists a solution T ⊆ H that is a directed tree and has cost at most C.
Moreover for every path Pi in T from the root a to some target bi , as we traverse Pi from a
to bi , the earliest necessary times of the edges are non-decreasing.
Proof of Claim 4.7. Consider a partition of H into edge-disjoint subgraphs H1 , . . . , Hk ,
where Hi is the subgraph whose edges have earliest necessary time ti . Clearly each Hi is a
single component.
If there is a directed cycle or parallel paths in the first subgraph H1 , then there is an edge
e ∈ E(H1 ) whose removal does not cause H1 to satisfy fewer demands at time t1 . Moreover
by monotonicity, removing e also does not cause H to satisfy fewer
at any future
S demands

k
times. Hence there exists a directed tree T1 ⊆ H1 such that T1 ∪
i=2 Hi has cost at most
C and still satisfies D.
S

Sj
j
Now suppose by induction that for some j ∈ [k −1], i=1 Ti is a tree such that
i=1 Ti ∪
S

S

k
j
i=1 Ti ∪
i=j+1 Hi has cost at most C and satisfies D. Consider the partial solution
Hj+1 ; if this subgraph is not a directed tree, then there must be an edge (u, v) ∈ E(Hj+1 ) such
that v has another in-edge in the subgraph. However by monotonicity, (u, v) does not help
satisfy any new demands, as v is already reached by some other path
from the
S
 root.
S Hence by

j+1
k
removing all such redundant edges, we have Tj+1 ⊆ Hj+1 such that
T
∪
H
i
i
i=1
i=j+2
has cost at most C and satisfies D, which completes the inductive step.
Sk
We conclude that T := i=1 Ti ⊆ H is a tree of cost at most C satisfying D. Observe also
that by construction, T has the property that if we traverse any a → bi path, the earliest
necessary times of the edges never decrease.
J

CVIT 2016

23:10

Steiner Network Problems on Temporal Graphs

Now let T be the k-DTSN solution guaranteed to exist by Claim 4.7. Consider the
subgraph H 0 ⊆ G0 formed by adding, for each (u, v) ∈ E(T ), the edge (ut , v t ) ∈ E 0 where t
is the earliest necessary time of (u, v) in E(H). In addition, add all the free edges (v i , v i+1 ).
Since w(ut , v t ) = w(u, v) by construction, cost(H 0 ) ≤ cost(T ) ≤ C.
To see that H 0 is a valid solution, consider any demand (a1 , btii ). Recall that T has a
unique a → bi path Pi along which the earliest necessary times are nondecreasing. We added
to H 0 each of these edges at the level corresponding to its earliest necessary time; moreover,
whenever there are adjacent edges (u, v), (v, x) ∈ Pi with earliest necessary times t and
0
0
t0 ≥ t respectively, there exist in H 0 free edges (v t , v t+1 ), . . . , (v t −1 , v t ). Thus H 0 contains
an a1 → btii path, which completes the proof.
J
I Lemma 4.8. If the constructed DST instance (G0 , D0 ) has a solution of cost C, then the
original k-DTSN instance (G1 , . . . , GT , D) has a solution of cost at most C.
Proof. First note that any DST solution ought to be a tree; let T 0 ⊆ G0 be such a solution
of cost C. For each (u, v) ∈ G, T 0 might as well use at most one edge of the form (ui , v i ),
since if it uses more, it can be improved by using only the one with minimum i, then
taking the free edges (v i , v i+1 ) as needed. We create a k-DTSN solution T ⊆ G as follows:
for each (ui , v i ) ∈ E(T 0 ), add (u, v) to T . Since w(u, v) = w(ui , v i ) by design, we have
cost(T ) ≤ cost(T 0 ) ≤ C. Finally, since each a1 → btii path in G0 has a corresponding path in
G by construction, T satisfies all the demands.
J
Lemma 4.5 follows from Lemma 4.6 and Lemma 4.8. Finally we get the main result of
this subsection:
I Theorem 1.3. Monotonic Single-Source k-DTSN has a polynomial-time O(k  )-approximation
algorithm for every  > 0. It has no Ω(log2− n)-approximation algorithm unless NP ∈
ZPTIME(npolylog(n) ).
Proof. This follows by composing the reduction with the algorithm of Charikar et al. [6] for
Directed Steiner Tree, which achieves ratio O(k  ) for every  > 0. More precisely they give a
i2 (i − 1)k 1/i -approximation for any integer i ≥ 1, in time O(ni k 2i ). The lower bound follows
from the known hardness of DST due to Halperin and Krauthgamer [16].
J
In Appendix D, we show how to modify the algorithm of Charikar et al. to arrive at
a simple, explicit algorithm for Monotonic Single-Source k-DTSN achieving the same upper
bound as Theorem 1.3.

5

Discussion

Our upper bound on the single-source monotonic directed case leaves the following open:
I Open Question 5.1. Is there a nontrivial approximation algorithm for the monotonic
directed problem with arbitrary demands?
It would be particularly elegant if this could be resolved by reducing the problem to
Directed Steiner Network, just as the single-source case was reduced to Directed Steiner Tree.
However this seems to require new techniques, as a simple counterexample shows that
Claim 4.7 does not hold for multi-source demands.
Secondly, our reduction from k-Partite Hypergraph Label Cover to the temporal Steiner
problems depends, in more than one way, on k being fixed. One might hope, then, to
obtain a nontrivial approximation in terms of n and T instead of k. When k = Θ(n2 T ), the

A. Khodaverdian, B. Weitz, J. Wu, and N. Yosef

23:11

shortest paths heuristic only guarantees a ratio of O(n2 T ). Using an algorithm of [15] that
approximates DSN to within O(n4/5+ ), we can improve this to O(n4/5+ · T ).
On the complexity side, the current best approximation lower bound for k-DTSN purely
1−
in terms of n is the same as that for DSN: Ω(2log n ) unless NP has quasipolynomial-time
algorithms [12]. Recall a conceptual message of Theorem 1.1: if we seek an approximation
in terms of k, then the best we can do is to consider the graph at each individual time (in
the reduction, each demand occurred at a separate time). We ask if there is a strong lower
bound that demonstrates a similar message when trying to approximate in terms of n and T :
I Open Question 5.2. For k-TSN or k-DTSN, is there a better approximation algorithm in
1−
terms of n and/or T ? Can we show an inapproximability of Ω(T · 2log n )?

References
1

2

3

4

5

6

7

8

9

10
11

Ajit Agrawal, Philip Klein, and R Ravi. When trees collide: An approximation algorithm for
the generalized steiner problem on networks. SIAM Journal on Computing, 24(3):440–456,
1995.
Sanjeev Arora, László Babai, Jacques Stern, and Z Sweedy. The hardness of approximate
optima in lattices, codes, and systems of linear equations. In Foundations of Computer
Science, 1993. Proceedings., 34th Annual Symposium on, pages 724–733. IEEE, 1993.
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof
verification and the hardness of approximation problems. Journal of the ACM (JACM),
45(3):501–555, 1998.
Taly Ben-Shitrit, Nir Yosef, Keren Shemesh, Roded Sharan, Eytan Ruppin, and Martin Kupiec. Systematic identification of gene annotation errors in the widely used yeast mutation
collections. Nat Meth, 9(4):373–378, 04 2012.
Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. An improved lpbased approximation for steiner tree. In Proceedings of the forty-second ACM symposium
on Theory of computing, pages 583–592. ACM, 2010.
Moses Charikar, Chandra Chekuri, To-yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha,
and Ming Li. Approximation algorithms for directed steiner problems. Journal of Algorithms, 33(1):73–91, 1999.
Moses Charikar, Joseph Naor, and Baruch Schieber. Resource optimization in qos multicast
routing of real-time multimedia. IEEE/ACM Transactions on Networking, 12(2):340–348,
2004.
Andrew Chatr-aryamontri, Bobby-Joe Breitkreutz, Rose Oughtred, Lorrie Boucher, Sven
Heinicke, Daici Chen, Chris Stark, Ashton Breitkreutz, Nadine Kolas, Lara O’Donnell,
Teresa Reguly, Julie Nixon, Lindsay Ramage, Andrew Winter, Adnane Sellam, Christie
Chang, Jodi Hirschman, Chandra Theesfeld, Jennifer Rust, Michael S Livstone, Kara Dolinski, and Mike Tyers. The biogrid interaction database: 2015 update. Nucleic Acids Research,
43(Database issue):D470–D478, 01 2015. doi:10.1093/nar/gku1204.
Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev. Set connectivity problems
in undirected graphs and the directed steiner network problem. ACM Transactions on
Algorithms (TALG), 7(2):18, 2011.
Miroslav Chlebík and Janka Chlebíková. The steiner tree problem on graphs: Inapproximability results. Theoretical Computer Science, 406(3):207–214, 2008.
Julia Chuzhoy, Anupam Gupta, Joseph Seffi Naor, and Amitabh Sinha. On the approximability of some network design problems. ACM Transactions on Algorithms (TALG),
4(2):23, 2008.

CVIT 2016

23:12

Steiner Network Problems on Temporal Graphs

12

13
14

15

16

17
18
19

20

21

22
23

24

25

A

Yevgeniy Dodis and Sanjeev Khanna. Designing networks with bounded pairwise distance.
In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages
750–759. ACM, 1999.
Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM),
45(4):634–652, 1998.
Jon Feldman and Matthias Ruhl. The directed steiner network problem is tractable for a
constant number of terminals. In Foundations of Computer Science, 1999. 40th Annual
Symposium on, pages 299–308. IEEE, 1999.
Moran Feldman, Guy Kortsarz, and Zeev Nutov. Improved approximating algorithms for
directed steiner forest. In Proceedings of the twentieth Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 922–931. Society for Industrial and Applied Mathematics, 2009.
Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In Proceedings
of the thirty-fifth annual ACM symposium on Theory of computing, pages 585–594. ACM,
2003.
Christopher S Helvig, Gabriel Robins, and Alexander Zelikovsky. An improved approximation scheme for the group steiner problem. Networks, 37(1):8–20, 2001.
Shao-shan Carol Huang and Ernest Fraenkel. Integration of proteomic, transcriptional, and
interactome data reveals hidden signaling components. Science signaling, 2(81):ra40, 2009.
Evgeny Kanshin, Louis-Philippe Bergeron-Sandoval, S. Sinan Isik, Pierre Thibault, and
Stephen W. Michnick. A cell-signaling network temporally resolves specific versus promiscuous phosphorylation. Cell Reports, 10(7):1202 – 1214, 2015. doi:http://dx.doi.org/
10.1016/j.celrep.2015.01.052.
Arnon Mazza, Irit Gat-Viks, Hesso Farhan, and Roded Sharan. A minimum-labeling approach for reconstructing protein networks across multiple conditions. Algorithms for Molecular Biology, 9(1):1, 2014.
Teresa M. Przytycka, Mona Singh, and Donna K. Slonim. Toward the dynamic interactome:
it’s about time. Briefings in Bioinformatics, 11(1):15–29, 2010. URL: http://dx.doi.org/
10.1093/bib/bbp057, doi:10.1093/bib/bbp057.
Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763–803, 1998.
Michelle S Scott, Theodore Perkins, Scott Bunnell, François Pepin, David Y Thomas, and
Michael Hallett. Identifying regulatory subnetworks for a set of genes. Molecular & Cellular
Proteomics, 4(5):683–692, 2005.
Chuan Wu, Nir Yosef, Theresa Thalhamer, Chen Zhu, Sheng Xiao, Yasuhiro Kishi, Aviv
Regev, and Vijay K. Kuchroo. Induction of pathogenic th17 cells by inducible salt-sensing
kinase sgk1. Nature, 496(7446):513–517, 04 2013.
Nir Yosef, Lior Ungar, Einat Zalckvar, Adi Kimchi, Martin Kupiec, Eytan Ruppin, and
Roded Sharan. Toward accurate reconstruction of functional protein networks. Molecular
systems biology, 5(1):248, 2009.

Problem Variants

There are several natural ways to formulate the temporal Steiner network problem, depending
on whether the edges are changing over time, or the nodes, or both.
I Definition 1.1 (k-Temporal Steiner Network (edge variant)). This is the formulation described in the Introduction: the inputs are G1 = (V, E1 ), . . . , GT = (V, ET ), w(·), and
D = {(ai , bi , ti )}. The task is to find a minimum-weight subgraph H ⊆ G that satisfies all of
the demands.
I Definition 1.2 (k-Temporal Steiner Network (node variant)). Let the underlying graph be
G = (V, E). The inputs are G1 = (V1 , E(V1 )), . . . , GT = (VT , E(VT )), w(·), and D. Here,

A. Khodaverdian, B. Weitz, J. Wu, and N. Yosef

23:13

E(Vt ) ⊆ E denotes the edges induced by Vt ⊆ V . A path satisfies a demand at time t iff all
edges along that path exist in Gt .
I Definition 1.3 (k-Temporal Steiner Network (node and edge variant)). The inputs are
G1 = (V1 , E1 ), . . . , GT = (VT , ET ), w(·), and D. This is the same as the node variant except
that each Et can be any subset of E(Vt ).
Similarly, define the corresponding directed problem k-Directed Temporal Steiner Network
(k-DTSN) with the same three variants. The only difference is that the edges are directed,
and a demand (a, b, t) must be satisfied by a directed a → b path in Gt .
The following observation enables all our results to apply to all problem variants.
I Proposition 2.1. The edge, node, and node-and-edge variants of k-TSN are mutually
polynomial-time reducible via strict reductions (i.e. preserving the approximation ratio exactly).
Similarly all three variants of k-DTSN are mutually strictly reducible.
Proof. The following statements shall hold for both undirected and directed versions. Clearly
the node-and-edge variant generalizes the other two. It suffices to show two more directions:
(Node-and-edge reduces to node) Let (u, v) be an edge existent at a set of times τ (u, v),
whose endpoints exist at times τ (u) and τ (v). To make this a node-temporal instance,
create an intermediate node x(u,v) existent at times τ (u, v), an edge (u, x(u,v) ) with the
original weight w(u, v), and an edge (x(u,v) , v) with zero weight. A solution of cost W
in the node-and-edge instance corresponds to a node-temporal solution of cost W , and
vice-versa.
(Node reduces to edge) Let (u, v) be an edge whose endpoints exist at times τ (u) and τ (v).
To make this an edge-temporal instance, let (u, v) exist at times τ (u, v) := τ (u) ∩ τ (v).
Let every node exist at all times; let the edges retain their original weights. A solution of
cost W in the node-temporal instance corresponds to an edge-temporal solution of cost
W , and vice-versa.
J

B

Inapproximability for General k

Here we prove our main theorem, showing optimal hardness for any number of demands. To
do this, we introduce a generalization of Label Cover to partite hypergraphs:
I Definition 2.1 (k-Partite Hypergraph Label Cover (k-PHLC)). An instance of this problem
consists of a k-partite, k-regular hypergraph G = (V1 , . . . , Vk , E) (that is, each edge contains
exactly one vertex from each of the k parts) and a set of possible labels Σ. The input also
includes, for each hyperedge e ∈ E, a projection function πve : Σ → C for each v ∈ e; Π is the
Sk
set of all such functions. A labeling of G is a function φ : i=1 Vi → Σ assigning each node a
label. There are two notions of edge satisfaction under a labeling φ:
φ strongly satisfies a hyperedge e = (v1 , . . . , vk ) iff the labels of all its vertices are mapped
to the same color, i.e. πvei (φ(vi )) = πvej (φ(vj )) for all i, j ∈ [k].
φ weakly satisfies a hyperedge e = (v1 , . . . , vk ) iff there exists some pair of vertices vi ,
vj whose labels are mapped to the same color, i.e. πvei (φ(vi )) = πvej (φ(vj )) for some
i 6= j ∈ [k].
I Theorem 2.2. For every  > 0 and every fixed integer k ≥ 2, there is a constant |Σ| such
that the following promise problem is NP-hard: Given a k-Partite Hypergraph Label Cover
instance (G, Σ, Π), distinguish between the following cases:

CVIT 2016

23:14

Steiner Network Problems on Temporal Graphs

(YES instance) There exists a labeling of G that strongly satisfies every edge.
(NO instance) Every labeling of G weakly satisfies at most |E| edges.
Theorem 2.2 follows from Feige’s k-prover system [13] by taking the number of repetitions
to be (a constant depending on k and ) large enough so that the error probability drops
below .
The proof of (k − )-hardness follows the same outline as the k = 2 case (Theorem 3.2).
I Theorem 1.1 (Main Theorem). k-TSN and k-DTSN are NP-hard to approximate to a
factor of k −  for every k ≥ 2 and every constant  > 0. For k-DTSN, this holds even when
the underlying graph is acyclic.
Proof. Given the k-PHLC instance (G = (V1 , . . . , Vk , E), Σ, Π), and letting vt,i denote the
i-th node in Vt , construct a k-DTSN instance (G = (G1 , . . . , Gk ), along with k demands)
S
S
as follows. For every t ∈ [k], create nodes vt,1
, . . . , vt,|V
. Create a vt,i -bundle from each
t |+1
S
S
vt,i
to vt,i+1
, whose `-strands (for ` ∈ Σ) are each a chain of bundles, one for each incident
hyperedge e = (v1,i1 , . . . , vt,i , . . . , vk,ik ) ∈ E. Each (v1,i1 , . . . , vt,i , . . . , vk,ik )-bundle has a
(v1,i1 , `1 , . . . , vt,i , `t , . . . , vk,ik , `k )-path for each agreeing combination of labels—that is, every
k-tuple (`1 , . . . , `t , . . . , `k ) such that πve1,i1 (`1 ) = · · · = πvet,i (`t ) = · · · = πvek,i (`k ), where e
k
is the shared edge. If there are no such combinations, then the e-bundle is a single simple
strand.
For each t ∈ [k], set all the edges in the vt,i -bundles to exist in Gt only. Now, for each
(v1,i1 , `1 , . . . , vk,ik , `k ), merge together the (v1,i1 , `1 , . . . , vk,ik , `n
k )-paths across all
 Gt that
o
have such a strand. Finally, the connectivity demands are D =

S
S
vt,1
, vt,|V
, t : t ∈ [k] .
t |+1

The analysis follows the k = 2 case. Suppose we have a YES instance of k-PHLC, with
Sk
optimal labeling `∗v to each node v ∈ t=1 Vt . Then an optimal solution H∗ to the constructed
k-DTSN instance is to traverse, at each time t and for each vt,i -bundle, the path through
the `∗vt,i -strand. In particular for each (v1,i1 , . . . , vk,ik )-bundle in that strand, traverse the
(v1,i1 , `∗1 , . . . , vk,ik , `∗k )-path.
In tallying the total edge cost, H∗ ∩ G1 (the subgraph at time 1) incurs a cost of |E|, one
for each contact edge. The subgraphs of H∗ at times 2, . . . , k account for no additional cost,
since all contact edges correspond to a label which agrees with all its neighbors’ labels, and
hence were merged with the agreeing contact edges in the other subgraphs.
Conversely suppose we have a NO instance of k-PHLC, so that for any labeling `∗v , for at
least (1 − )|E| hyperedges e, the projection functions of all nodes in e disagree. By definition,
S
S
any solution to the constructed k-DTSN instance contains a simple vt,1
→ vt,|V
path Pt
t |+1
at each time t. As before, P1 alone incurs a cost of exactly |E|. However, at least (1 − )|E|
of the hyperedges in G cannot be weakly satisfied; for these hyperedges e, for every pair of
neighbors vt,it , vt0 ,it0 ∈ e, there is no path through the e-bundle in vt,it ’s `∗vt,it -strand that is
merged with any of the paths through the e-bundle in vt0 ,it0 ’s `∗vt,i 0 -strand (for otherwise, it
t
would indicate a labeling that weakly satisfies e in the k-PHLC instance). Therefore paths
P2 , . . . , Pk each contribute at least (1 − )|E| additional cost, so the solution has total cost
at least (1 − )|E| · k.
The directed temporal graph we constructed is acyclic. It follows from the gap between
the YES and NO cases that k-DTSN is NP-hard to approximate to within a factor of k −  for
every constant  > 0, even on DAGs. As before, the same analysis holds for the undirected
problem k-TSN by undirecting the edges.
J

A. Khodaverdian, B. Weitz, J. Wu, and N. Yosef

C

23:15

An Exact Algorithm

We can derive a natural integer linear program for k-DTSN by first reducing it to a simpler
special case, then writing the ILP for this simpler version. The simplified case we consider is
one in which all demands share a source and target, and each demand occupies a distinct
time.
I Definition 3.1 (Simple k-DTSN (node variant)). This is the special case of k-DTSN in
which the demands are precisely (a, b, 1), (a, b, 2), . . . , (a, b, k), for some common a, b ∈ V .
The following reduction demonstrates that demands can always be simplified at the expense
of more time points.
I Lemma 3.2 (k-DTSN reduces to Simple k-DTSN (node variant)). An instance of k-DTSN
with underlying graph G = (V, E) and k demands (not necessarily at distinct times) can
be converted to an instance of Simple k-DTSN with 2k + |V | nodes, 2k + |E| edges, and k
demands at distinct times.
Proof. Suppose we are given an instance of k-DTSN with temporal graph G = (G1 , . . . , GT ),
underlying graph G = (V, E), and demands D = {(ai , bi , ti ) : i ∈ [k]}. By Proposition 2.1, we
can assume this is a node-temporal instance. We build a new instance with temporal graph
G 0 = (G01 , . . . , G0T ), underlying graph G0 = (V 0 , E 0 ), and demands D0 .
Initialize G 0 to G. Define a new set of times [k]. Add to G 0 the new nodes a and b, which
exist at all times/in all frames Gi . For all v ∈ V and i ∈ [k], if v ∈ Gti , then let v exist in G0i
as well. For each (ai , bi , ti ) ∈ D,
1. Create new nodes xi , yi . Create zero-weight edges (a, xi ), (xi , ai ), (bi , yi ), and (yi , b).
2. Let xi and yi exist only in frame G0i .
Lastly, the demands are D0 = {(a, b, i) : i ∈ [k]}.
Given a solution H0 ⊆ G 0 containing an a → b path at every time i ∈ [k], we can simply
exclude nodes a, b, {xi }, and {yi } to obtain a solution H ⊆ G to the original instance, which
contains an ai → bi path in Gti for all i ∈ [k], and has the same cost. The converse is also
true by including these nodes.
J
The node variant of Simple k-DTSN has a natural integer programming formulation in
terms of flows:
X

minimize

duv · w(u, v)

(1)

(u,v)∈E

duv ≥ duvt

subject to
X
(u,v)∈Et

duvt −

X

∀t ∈ [T ], (u, v) ∈ Et

(2)

dvwt = 0

∀t ∈ [T ], v ∈
/ {a, b}

(3)

daut = 1

∀t ∈ [T ]

(4)

dubt = 1

∀t ∈ [T ]

(5)

duvt ∈ {0, 1}

∀t ∈ [T ], (u, v) ∈ Et

(6)

(v,w)∈Et

X
(a,u)∈Et

X
(u,b)∈Et

Each variable duvt denotes the flow through edge (u, v) at time t, if it exists. Constraint
(2) ensures that if an edge is used at any time, it is chosen as part of the solution subgraph.

CVIT 2016

23:16

Steiner Network Problems on Temporal Graphs

(3) enforces flow conservation at all nodes and all times. (4) and (5) impose non-zero flow
from a to b at all times.
We implemented the reduction of Theorem 3.2 and the above ILP in Python, using Gurobi optimization software (code is available at: https://github.com/YosefLab/
dynamic_connectivity).

D

Explicit Algorithm for Monotonic Single-Source k-DTSN

We provide a modified version of the approximation algorithm presented in Charikar et
al. [6] for Directed Steiner Tree (DST), which achieves the same approximation ratio for our
problem Monotonic Single-Source k-DTSN.
We provide a similar explanation as of that presented in Charikar et al. Consider a trivial
approximation algorithm, where we take the shortest path from the source to each individual
target. Consider the example where there are edges of cost C −  to each target, and a
vertex v with distance C from the source, and with distance 0 to each target. In such a case,
this trivial approximation algorithm will have an O(k) approximation. Consider instead, an
algorithm which found from the root, an intermediary vertex v, which was connected to
all the targets via shortest path. In the case of the above example, this would find us the
optimal subgraph. The algorithm below generalizes this process, by progressively finding
optimal substructures with good cost relative to the number of targets connected. We show
that this algorithm provides a good approximation ratio.
I Definition 4.1 (Metric closure of a temporal graph). For a directed temporal graph G =
(G1 = (V, E1 ), G2 = (V, E2 ), . . . , GT = (V, ET )), define its metric closure to be G̃ = (V, E, w̃)
S
where E = t Et and w̃(u, v, t) is the length of the shortest u → v path in Gt (note that in
contrast with w, w̃ takes three arguments).
I Definition 4.2 (V (T )). Let T be a tree with root r. We say a demand of the form (r, b, t)
is satisfied by T if there is a path in T from r to b at time t. V (T ) is then the set of demands
satisfied by T .
I Definition 4.3 (D(T )). The density of a tree T is D(T ) = cost(T )/|V (T )|, where cost(T )
is the sum of edge weights of T .

1: function Ai (transitive closure G = (V, E, w), r, t, k, D ⊆ V × [T ])
2:

if (r, bi , ti ) does not exist for least k(bi , ti ) ∈ D, ti ≥ t then return no solution

3:

T ←∅
while k > 0 do
Tbest ← ∅
for all (v, t0 ) ∈ V × [T ], t0 ≥ t and k 0 , 1 ≥ k 0 ≥ k do
T 0 ← Ai−1 (G, v, t0 , k 0 , D) ∪ (r, v, t0 )
if d(TBEST ) > d(T 0 ) then TBEST ← T 0 . Demand i satisfied only if edge to
bi at ti (ie (x, bi , ti ) for some x)

4:
5:
6:
7:
8:
9:
10:

T ← T ∪ TBEST ; k ← k − |D ∩ V (TBEST )|; X ← X − V (TBEST )
return T

The way we will prove the approximation ratio of this algorithm is to show that it behaves
precisely as the algorithm of Charikar et al. does, when given as input the DST instance
produced by our reduction from Monotonic Single-Source k-DTSN (Lemma 4.5).

A. Khodaverdian, B. Weitz, J. Wu, and N. Yosef

23:17

I Proposition 4.4. The algorithm above is equivalent to the algorithm of Charikar et al.,
when applied to the DST instance output by the reduction of Lemma 4.5.
Proof. To see this, note that in our reduced instance, we see a collection of vertices, v 1 , ..., v |T | .
Therefore, the only equivalent modification’s needed to the original algorithm are:
In the input, rather than keeping track of the current root as some vertex v i , keep track
of v at the current timepoint instead, i.e. (v, i).
The distance from some v i to xj , j ≥ i is simply the distance from v to x at time j, i.e.
w̃(v, x, j).
Instead of looping through all vertices in the form v 1 , . . . , v |T | , we instead loop through
all vertices, and all time points.
Therefore this algorithm guarantees the same approximation ratio for Monotonic Single-Source
k-DTSN as the original algorithm achieved for DST. In particular for all i > 1, Ai (G, a, 0, k, D)
provides an i2 (i − 1)k 1/i approximation to k-DTSN, in time O(ni k 2i ) [6, 17]1 .
J

E

Applications to Computational Biology

In molecular biology applications, networks are routinely defined over a wide range of basic
entities such as proteins, genes, metabolites, or drugs, which serve as nodes. The edges in these
networks can have different meaning, depending on the particular context. For instance, in
protein-protein interaction (PPI) networks, edges represent physical contact between proteins,
either within stable multi-subunit complexes or through transient causal interactions (i.e.,
an edge (x, y) means that protein x can cause a change to the molecular structure of protein
y and thereby alter its activity). The body of knowledge encapsulated within the human
PPI network (tens of thousands of nodes and hundreds of thousands of edges in current
databases, curated from thousands of studies [8]) is routinely used by computational biologists
to generate hypotheses of how various signals are transduced in eukaryotic cells [24]. The
basic premise is that a process that starts with a change to the activity of protein u and ends
with the activity of protein v must be propagated through a chain of interactions between
u and v. The natural extension regards a process with a certain collection of protein pairs
{(u1 , v1 ), . . . , (uk , vk )}, where we are looking for a chain of interactions between each ui
and vi . In most applications, the identity of ui and vi is assumed to be known (or inferred
from experimental data), while the identity of the intermediate nodes and interactions is
unknown. The goal therefore becomes to complete the gap and find a probable subgraph of
the PPI network that simultaneously enables signals between all the protein pairs, thereby
explaining the overall biological activity. Since the edges in the PPI network can be assigned
a probability value (reflecting the credibility of their experimental evidence), by taking the
negative log of these values as edge weights, the task becomes minimizing the total edge
weight, leading to an instance of the Steiner network problem. We have previously used this
approach to study the propagation of a stabilizing signal in pro-inflammatory T cells, leading
to the identification of a new molecular pathway (represented by a subgraph of the PPI
network) that is critical for mounting an auto-immune response, as validated experimentally
by perturbation assays and disease models in mice [24]. Variations on this idea have been
used successfully by [23], [18], [25], [4] and others.
While these studies contributed to the understanding of signal transduction pathways in
living cells, they ignore a critical aspect of the underlying biological complexity. In reality,

1

The first paper [6] incorrectly claims a bound of i(i − 1)k1/i ; this was corrected in [17].

CVIT 2016

23:18

Steiner Network Problems on Temporal Graphs

proteins (nodes) can become activated or inactivated at different points in time and with
different dynamics, thereby giving rise to a PPI network that changes over time [21]. Recent
advances in mass-spectrometry based measurements provide a way to estimate these changes
at high throughput (e.g., measuring phosphorylation levels or overall protein abundance,
proteome-wide) [19]. The next challenge is therefore to study connectivity problems that
take into account not only the endpoints of each demand, but also the time (or condition) in
which this demand should be satisfied. This added complication was tackled by Mazza et
al. [20], who introduced the “Minimum k-Labeling (MKL)” problem. In this setting, each
connectivity demand comes with a label, which represents a certain experimental condition or
time point. The task is to label edges in the PPI network so as to satisfy each demand using
its respective label, while minimizing the number of edges in the resulting subgraph and the
number of labels used to annotate these edges. They give a brief theoretical analysis of MKL,
then present an ILP-based algorithm that works well in several experiments. While MKL was
an important first step, the challenge remains to satisfy connectivity demands for different
conditions, while taking into account changes to the activity of proteins under each condition,
thus providing more reliable hypotheses for the mechanism of signal transduction. Simplifying
the experimentally-measured activity of proteins to a binary view of presence/absence, the
work presented here aims to address this challenge.
Our formulation of the TSN problem naturally arises from our work on PPI networks:
the nodes V represent proteins; the edges E represent protein interactions, weighed by the
confidence of the supporting experimental data (for e ∈ E, w(e) = − log(p(e)) where p(e) is
the probability associated with interaction e); the existence function σ can be derived from a
proteome-wide assay, e.g., measuring protein abundance or phospnorylation levels over a set
of T time points or experimental conditions. Notably, while in this setting we assign states
of presence/absence to proteins (nodes), it is mutually polynomial-time reducible with the
formulation above (where the existence function is defined over the edges; see Proposition 2.1).
The connectivity demands include pairs of proteins (a, b) that represent the known end points
of an unknown signal transduction cascade that is active in experimental condition t ∈ [T ].
Finally, the desired output is a maximum-probability subgraph of the PPI network G that
explains the transduction of signals between all the queried protein pairs in the respective
experimental condition, while taking into account the experimentally-derived information of
protein presence/absence.

