2016/09/16 by Alex Khodaverdian, Benjamin Weitz, Khodaverdian, Alex +5 · 1 citation
Biochemistry, Genetics and Molecular Biology · Engineering · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Genome Rearrangement Algorithms #Single-cell and spatial transcriptomics #Slime Mold and Myxomycetes Research
paper · pdf · doi:10.48550/arxiv.1609.04918
openalex publication_date 2016/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.