Simultaneous Network Design with Restricted Link Usage

Naonori Kakimura, Péter Madarasi, Jannik Matuschke, Kitti VargaarXiv 2025 · DOI · arXiv

Abstract

The Simultaneous Path Problem addresses network design where a single infrastructure must accommodate multiple commodities, each restricted to specific link subsets. This paper explores the complexity of finding minimum-cost edge subsets that provide valid paths for all commodities. While generally NP-hard and difficult to approximate, the problem is shown to be tractable for directed acyclic graphs (DAGs) with a fixed number of commodities or when link restrictions follow a hierarchical laminar structure.

Introduction

In a standard shortest-path problem, the goal is to find the cheapest route from point A to point B. However, real-world networks are rarely that simple. Consider a city's transportation grid: a single set of roads must serve cars, buses, and bicycles. Not every road is open to every vehicle—buses have dedicated lanes, and bikes might be barred from highways.

An example of a network with two commodities (red rectangles and blue triangles) and their restricted link usage.

This paper formalizes this challenge as Simultaneous Network Design with Restricted Link Usage. Given a graph where edges are assigned "colors" (representing allowed usage for different commodities), the objective is to find a minimum-cost subset of edges such that every commodity has a valid path from a source $s$ to a destination $t$ using only its allowed edges.

Problem Variants

The authors distinguish between two primary flavors of the problem:

  1. The Superset Variant: The chosen network must contain a valid path for each color.
  2. The Exact Variant: The portion of the chosen network accessible to a specific color must be exactly a single path.

Methodology

The research employs a combination of complexity theory and algorithmic design to map the problem's landscape:

  • Hardness Reductions: The authors prove the problem's difficulty by reducing known NP-hard problems (such as 3SAT, Set Cover, and Disjoint Paths) to variants of the Simultaneous Path Problem.
  • Dynamic Programming (DP): For Directed Acyclic Graphs (DAGs), they construct an auxiliary "product graph" where nodes represent the simultaneous positions of all $k$ commodities. This allows for optimal solutions using shortest-path algorithms on the expanded graph.
  • Fixed-Parameter Tractability (FPT): Recognizing that complexity often stems from "multi-colored" arcs (links usable by many commodities), they developed algorithms that run efficiently if the number of such overlapping links is small.
  • Structural Analysis: The study explores "laminar" families—link restrictions that are either nested or completely disjoint—demonstrating that these cases are significantly easier to solve.

Key Results

The paper provides a comprehensive map of the problem's difficulty across different graph types and constraints. A significant finding is the "Exact" penalty: requiring the intersection of the network and a color class to be exactly a path makes the problem significantly harder, remaining NP-complete even on DAGs.

Summary of complexity and approximability results for Simultaneous Path Problem variants.

Key takeaways include:

  • Hardness: Both directed and undirected versions are NP-complete even for just $k=2$ colors.
  • Inapproximability: For the Superset variant on DAGs, it is impossible to find a solution within a factor of $(1-\epsilon) \ln k$ of the optimum (unless P=NP), mirroring the hardness of the Set Cover problem.
  • Tractability: The problem becomes solvable in polynomial time if the number of colors $k$ is constant on a DAG, or if the color classes form a laminar family.

Conclusion and Future Work

The inherent hardness of the Simultaneous Path Problem suggests that general-purpose, efficient, and near-optimal algorithms are unlikely for large-scale, complex networks. Future research directions include extending the model to multiple terminal pairs (different sources $s_i$ and sinks $t_i$ for each commodity), investigating better approximation ratios for specific graph classes beyond DAGs, and exploring budget-constrained versions where connectivity is maximized for a fixed cost.

Summary updated

BibTeX
@misc{kakimura2025simultaneous,
  author = {Naonori Kakimura and Péter Madarasi and Jannik Matuschke and Kitti Varga},
  title = {{Simultaneous Network Design with Restricted Link Usage}},
  year = {2025},
  eprint = {2507.09426},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.09426},
}
Figure