Offline Directed Steiner Network Problems on Dynamic Graphs

Benjamin Weitz, Jimmy Wu, Nir YosefarXiv 2016 · arXiv

Steiner network problems are fundamental to combinatorial optimization, traditionally focusing on finding the minimum-cost subgraph that connects a set of terminal nodes in a static environment. However, real-world networks—from cellular signaling pathways to mobile communication links—are inherently dynamic. This paper explores the complexity of these problems in a "temporal" setting, where the graph structure evolves over discrete time steps.

The $k$-Temporal Steiner Network Problem

The authors formalize the $k$-Temporal Steiner Network ($k$-TSN) problem. In this model, we are given a sequence of graph frames $(G_1, G_2, \dots, G_T)$ and $k$ connectivity demands. Each demand $(a, b, t)$ requires that nodes $a$ and $b$ be connected by a path existing entirely within the graph at time $t$. The objective is to find a minimum-weight subgraph of the underlying graph (the union of all frames) that satisfies all $k$ demands.

Complexity and Hardness

A central finding of the research is that the addition of a time dimension fundamentally increases problem difficulty. The authors prove that $k$-TSN and its directed version ($k$-DTSN) are NP-hard to approximate within a factor of $k - \epsilon$ for any $k \ge 2$, even when the underlying graph is a Directed Acyclic Graph (DAG).

To establish this hardness, the authors employ a reduction from the Label Cover problem, constructing intricate gadgets where paths represent specific label assignments. This result implies that the "trivial" solution—finding the shortest path for each demand independently and taking their union—is essentially the best possible approximation in the general case.

A visual representation of the "bundle" and "strand" gadgets used to build the complexity reduction.

Monotonicity as a Bridge to Tractability

While the general temporal problem is highly resistant to approximation, the authors identify "monotonic" graphs as a more tractable subclass. In a monotonic graph, once an edge appears, it remains present for all subsequent time steps. This property reflects many biological processes, such as the synthesis of a protein that remains active throughout an experiment.

The paper proves that monotonic temporal problems can be mapped to established static variants:

  • Undirected Monotonic: Equivalent to the Priority Steiner Tree problem, allowing for an $O(\log k)$-approximation.
  • Directed Monotonic (Single-Source): Equivalent to the Directed Steiner Tree problem, allowing for an $O(k^\epsilon)$-approximation.

Key Insights and Applications

The study highlights that time acts as a complexity multiplier. Even with full knowledge of the graph's history (the "offline" setting), temporal constraints prevent the use of many sophisticated static approximation techniques. The core challenge lies in the way demands at different times must overlap to minimize cost.

A visualization of overlapping temporal demands (blue, red, and green) where shared edges minimize total network cost across different time steps.

Beyond theoretical analysis, the authors provide an Integer Linear Program (ILP) formulation based on network flows. This allows for exact solutions in practical applications where $k$ is small, such as inferring signaling pathways from Protein-Protein Interaction (PPI) databases like BioGRID.

Future Directions

Several open questions remain, particularly regarding the multi-source monotonic directed case, where demands have arbitrary sources and targets. The authors also suggest investigating approximation ratios in terms of the number of nodes ($n$) and time steps ($T$), potentially establishing even stricter lower bounds for temporal network optimization.

Summary updated

BibTeX
@misc{weitz2016offline,
  author = {Benjamin Weitz and Jimmy Wu and Nir Yosef},
  title = {{Offline Directed Steiner Network Problems on Dynamic Graphs}},
  year = {2016},
  eprint = {1609.04918},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1609.04918},
}
Figure