The Complexity of Routing with Few Collisions

Till Fluschnik, Marco Morik, Manuel Sorge

TL;DR

This paper maps the computational landscape of "Routing with Collision Avoidance" (RCA)—the task of finding multiple paths through a network that minimize simultaneous edge usage. The authors demonstrate that while finding simple paths or trails with few collisions is almost always computationally "hard" (NP-complete), allowing objects to wander (walks) makes the problem surprisingly solvable in polynomial time for undirected networks.

What Problem Does This Paper Address?

In traditional network routing, we often try to minimize "shared edges"—links used by more than one route. However, in the real world (traffic, data packets, logistics), two objects only "collide" if they use the same link at the same time.

The authors formalize this as the Routing with Collision Avoidance (RCA) problem: Given a graph, a source $s$, a sink $t$, and a budget of $p$ routes, can we ensure that no more than $k$ edges are shared at the exact same time step? They analyze this across three route types:

  1. Paths: No vertex can be visited more than once.
  2. Trails: No edge can be visited more than once.
  3. Walks: No restrictions on revisiting vertices or edges.

They also investigate a "Fast" variant (FRCA) where routes must be shorter than a given length $\alpha$.

Methods

The paper is a theoretical complexity study. The authors use two primary tools:

  • Hardness Reductions: To prove a problem is NP-complete, they reduce known hard problems—like the Planar Cubic Hamiltonian Cycle or Set Cover—to specific instances of RCA. This shows that if we could solve RCA quickly, we could solve these famous "unsolvable" problems quickly too.
  • Time-Expanded Networks: To prove tractability (polynomial time), they transform the dynamic, time-dependent graph into a static "time-expanded" version. In this expanded graph, a standard Max-Flow algorithm can find the optimal routes.

Datasets

As a theoretical computer science paper focused on complexity classes and proofs, no empirical datasets or training were used. The results are mathematical certainties based on the properties of graphs and algorithms.

Key Insights and Ideas

  • The "Walk" Loophole: The most striking insight is that Walk-RCA on undirected graphs is solvable in linear time. Why? Because if you are allowed to revisit edges, you can essentially "queue" at the starting node. One object leaves at time $t=1$, the next at $t=3$, and so on. By "waiting" at the start (shuttling back and forth on the first edge), you can avoid all collisions.
  • Length Restrictions Kill Tractability: The "queuing" strategy mentioned above requires very long walks. As soon as you add a length constraint ($\alpha$), the problem (Walk-FRCA) becomes NP-complete on undirected graphs.
  • DAGs are the Great Equalizer: On Directed Acyclic Graphs (DAGs), there is no difference between a path, a trail, or a walk (since you can never return to a previous node). Consequently, all three variants share the same complexity on DAGs: easy if the collision budget $k$ is constant, but hard if $k$ is part of the input.
  • Paths are Inherently Hard: Unlike the static "Minimum Shared Edges" problem, which is easy when the number of shared edges is small, the time-variant Path-RCA remains NP-complete even if you allow zero collisions ($k=0$).

Key Results

The authors provide a complete classification table for the problem (see Table 1 in the paper). Highlights include:

Route Type Undirected (const. $k$) Directed (const. $k$) DAGs (const. $k$)
Path-RCA NP-complete NP-complete Polynomial
Trail-RCA NP-complete NP-complete Polynomial
Walk-RCA Polynomial Polynomial Polynomial
Walk-FRCA Open Polynomial Polynomial
  • Path/Trail RCA: Proven NP-complete even on planar graphs with a maximum degree of 4 or 5.
  • Walk-RCA: Solvable in $O(m \cdot n \cdot (pn)^2)$ time on directed graphs for $k=0$.

Limitations and Future Work

  • The "Open" Cell: The complexity of Walk-FRCA on undirected graphs specifically when the collision budget $k$ is a constant remains an open question.
  • Graph Classes: The authors suggest investigating whether these problems become easier on specific graph structures, such as those with bounded treewidth (a common "shortcut" in complexity theory).
  • Parameterization: Future research could look at the number of routes ($p$) as a parameter. In many real-world scenarios, $p$ might be small, which could lead to "Fixed-Parameter Tractable" (FPT) algorithms that are fast in practice.

Summary updated

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 \({\text {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 \({\text {NP}}\)-complete on undirected graphs.
BibTeX
@inproceedings{fluschnik2017complexity,
  author = {Till Fluschnik and Marco Morik and Manuel Sorge},
  title = {{The Complexity of Routing with Few Collisions}},
  booktitle = {FCT},
  year = {2017},
  url = {https://openreview.net/forum?id=bLfVNiBJQ5},
}

Loading related content...

Figure