Travelling on Graphs with Small Highway Dimension

Yann Disser, Andreas Emil Feldmann, Max Klimm, Jochen Könemann

Abstract

The Travelling Salesperson Problem (TSP) and Steiner Tree Problem (STP) are classic NP-hard optimization problems that are generally APX-hard. However, transportation networks often exhibit a "highway dimension" property, where long-distance paths are covered by a small set of hubs. This paper provides the first Fully Polynomial-Time Approximation Scheme (FPTAS) for TSP and STP on graphs with highway dimension $h=1$. By establishing a structural relationship between highway dimension and treewidth, the authors demonstrate that these problems become tractable under specific topological constraints. Additionally, the paper proves that STP is weakly NP-hard at $h=1$ and TSP is NP-hard for $h \ge 6$, delineating the boundaries of computational tractability for these problems.

Introduction

In the study of network optimization, the Travelling Salesperson Problem (TSP) and the Steiner Tree Problem (STP) serve as benchmarks for algorithmic efficiency. In their most general forms, these problems are APX-hard, meaning that no polynomial-time algorithm can achieve an arbitrary approximation ratio unless $P=NP$. However, empirical observations of road networks suggest they are not "general" graphs. Instead, they possess a low highway dimension, a parameter introduced to model the efficiency of shortest-path queries in transit networks.

Intuitively, a graph has a small highway dimension if, for every scale $r$, any shortest path of length significantly greater than $r$ passes through one of a small number of "hubs" within any ball of radius $r$. While previous work established a quasi-polynomial time approximation scheme (QPTAS) for graphs with constant highway dimension, the existence of a true polynomial-time scheme remained an open question.

Algorithmic Framework: From Highway Dimension to Treewidth

The core of the authors' algorithmic contribution is the bridge built between the highway dimension and the graph's treewidth. Treewidth measures how closely a graph resembles a tree; problems that are NP-hard on general graphs often become solvable in polynomial time on graphs with bounded treewidth using dynamic programming.

1. Structural Analysis

The authors prove that for graphs where the highway dimension $h=1$, the treewidth is bounded by $O(\log \alpha)$, where $\alpha$ represents the aspect ratio (the ratio of the maximum to minimum edge weight). This is a significant structural insight, as it suggests that the "hub-and-spoke" nature of $h=1$ graphs prevents the formation of complex, highly intertwined structures.

2. Aspect Ratio Reduction

A treewidth logarithmic in $\alpha$ is not immediately useful if $\alpha$ is exponentially large. To address this, the authors employ a preprocessing technique to reduce the aspect ratio to a polynomial in $n/\epsilon$ (where $n$ is the number of vertices and $\epsilon$ is the error tolerance). This reduction is performed carefully to ensure that the optimal solution to the original problem can be recovered from the modified graph without violating the highway dimension constraints.

3. Dynamic Programming

With the graph transformed into one with $O(\log(n/\epsilon))$ treewidth, the authors apply standard dynamic programming algorithms. For TSP and STP, these algorithms run in time exponential in the treewidth but polynomial in the number of vertices. Given the logarithmic bound on treewidth, the resulting complexity is polynomial, yielding an FPTAS.

Complexity Boundaries

Beyond the positive algorithmic results, the paper provides rigorous hardness proofs that define the limits of what can be solved efficiently.

  • Steiner Tree Problem ($h=1$): The authors show that STP is weakly NP-hard on graphs with highway dimension 1 via a reduction from the Partition problem. This explains why an FPTAS is possible (as weak NP-hardness allows for approximation schemes) while a simple polynomial-time exact solution is unlikely.
  • Travelling Salesperson Problem ($h=6$): The paper settles a question open since 2015 by proving that TSP is NP-hard for graphs with highway dimension $h \ge 6$. This reduction from (3,3)-SAT demonstrates that even a relatively small increase in the highway dimension can lead to a "hard wall" in computational complexity.

Conclusion and Future Work

This research provides a definitive step forward in understanding the relationship between network topology and optimization complexity. By proving that $h=1$ allows for an FPTAS, the authors show that the simplest highway structures are computationally manageable.

However, several questions remain. The complexity of TSP for highway dimensions $2 \le h \le 5$ is still unknown. Furthermore, while a QPTAS exists for any constant $h$, it is currently unknown if a PTAS exists for $h > 1$. The authors conjecture that for $h > 1$, the treewidth may not be polylogarithmically bounded, suggesting that new algorithmic techniques moving beyond treewidth will be required to achieve polynomial-time approximations in higher dimensions.

Summary updated

BibTeX
@article{disser2021travelling,
  author = {Yann Disser and Andreas Emil Feldmann and Max Klimm and Jochen Könemann},
  title = {{Travelling on Graphs with Small Highway Dimension}},
  journal = {Algorithmica},
  year = {2021},
  doi = {10.1007/s00453-020-00785-5},
}
Figure