Abstract
We study the computational complexity of routing multiple objects through a network in such a way that only few collisions occur: Given a graph $G$ with two distinct terminal vertices and two positive integers $p$ and $k$, the question is whether one can connect the terminals by at least $p$ routes (e.g. paths) such that at most $k$ edges are time-wise shared among them. We study three types of routes: traverse each vertex at most once (paths), each edge at most once (trails), or no such restrictions (walks). We prove that for paths and trails the problem is NP-complete on undirected and directed graphs even if $k$ is constant or the maximum vertex degree in the input graph is constant. For walks, however, it is solvable in polynomial time on undirected graphs for arbitrary $k$ and on directed graphs if $k$ is constant. We additionally study for all route types a variant of the problem where the maximum length of a route is restricted by some given upper bound. We prove that this length-restricted variant has the same complexity classification with respect to paths and trails, but for walks it becomes NP-complete on undirected graphs.
Problem Definition
In traditional network routing, the goal is often to minimize shared edges. However, in dynamic systems like traffic or data packet transmission, two objects only "collide" if they occupy the same link at the same time. This paper formalizes this as the Routing with Collision Avoidance (RCA) problem.
The core question asks whether $p$ routes can be found between a source $s$ and a sink $t$ such that no more than $k$ edges are shared at the exact same time step. The authors analyze three route types:
- Paths: Vertices cannot be revisited.
- Trails: Edges cannot be revisited.
- Walks: No restrictions on revisiting vertices or edges.
Additionally, they consider the Fast RCA (FRCA) variant, where each route must have a length of at most $\alpha$.
Methods
The study employs theoretical complexity analysis using two primary techniques:
- Hardness Reductions: To establish NP-completeness, the authors reduce known hard problems (e.g., Planar Cubic Hamiltonian Cycle or Set Cover) to specific RCA instances. This demonstrates that a fast solution for RCA would imply fast solutions for these classically difficult problems.
- Time-Expanded Networks: To prove tractability for certain variants, the authors transform dynamic, time-dependent graphs into static "time-expanded" versions. In these expanded graphs, standard Max-Flow algorithms can be used to find optimal routes in polynomial time.
Key Insights
- The "Walk" Loophole: On undirected graphs, Walk-RCA is solvable in polynomial time. This is because objects can "wait" at the starting node by shuttling back and forth on the first edge, effectively queuing to avoid collisions.
- Length Restrictions and Tractability: The queuing strategy for walks requires potentially long routes. Introducing a length constraint ($\alpha$) in Walk-FRCA makes the problem NP-complete on undirected graphs.
- DAGs as a Special Case: On Directed Acyclic Graphs (DAGs), paths, trails, and walks are equivalent because cycles are impossible. Consequently, all variants share the same complexity: polynomial if the collision budget $k$ is constant, but NP-complete if $k$ is part of the input.
- Inherent Hardness of Paths: Unlike static edge-sharing problems, the time-variant Path-RCA is NP-complete even with zero allowed collisions ($k=0$).
Key Results
The authors provide a comprehensive classification of the complexity of RCA across different graph types and constraints.
Key findings include:
- Path/Trail RCA: These are NP-complete on both undirected and directed graphs, even for constant $k$ or bounded vertex degrees.
- Walk-RCA: Solvable in polynomial time on undirected graphs for arbitrary $k$, and on directed graphs for constant $k$.
- Walk-FRCA: While polynomial on directed graphs for constant $k$, it becomes NP-complete on undirected graphs for arbitrary $k$.
Future Work
Several avenues for further research remain:
- The "Open" Cell: The complexity of Walk-FRCA on undirected graphs with a constant collision budget $k$ is currently unknown.
- Structural Parameters: Investigating whether RCA becomes easier on graphs with specific properties, such as bounded treewidth.
- Parameterized Complexity: Exploring the number of routes ($p$) as a parameter, which might lead to Fixed-Parameter Tractable (FPT) algorithms useful for practical applications where $p$ is small.
Summary updated