Efficient Computation of Optimal Time-Division Multiplexing Disjoint Paths in Networks

Disjoint paths have attracted research interest for decades due to their applications in reliability, load balancing, and fault tolerance-particularly for mitigating network congestion. Yet strict edge disjointness is often too rigid for practical systems, as limited and controlled edge sharing can substantially improve throughput. Time-Division Multiplexing (TDM) is widely deployed to safely share edges across flows, suggesting a principled way to relax disjointness without sacrificing performance guarantees. We formalize this idea with the Time-Division Multiplexing Disjoint Paths (TDM-DP) problem: given a directed, weighted graph, find k source-destination paths that minimize total cost, comprising path weights plus explicit penalties for edge reuse, where penalties are incurred via sharing TDM-style time-slotting. Under a single-source setting we present a polynomial-time exact algorithm based on an improved augmenting path framework. We further provide rigorous proofs of correctness and optimality, primarily via mathematical induction. Our framework quantifies the trade-off between path efficiency and congestion, bridging the gap between hard disjointness and unconstrained sharing. Extensive experiments demonstrate that our algorithm matches the solution quality of integer-programming baselines while achieving significantly better runtime, comparable to a dijkstra-based greedy algorithm.