Improved efficient network design on planar graphs with small length slack

A Little Length Slack Goes a Long Way in Planar Length-Constrained Network Design

Data Structures and Algorithms

Summary

Designing networks that connect points with short paths can be very hard. The authors show that on flat (planar) layouts, allowing just a tiny bit of extra path length makes it much easier to find good network designs quickly. They created algorithms that nearly match the best possible solutions while only slightly increasing path lengths. They also prove it’s much harder to do this well on non-flat networks when the allowed path length increase is very small.

What this means in practice

  • For network planners: Design low-cost networks on planar layouts that connect points within strict distance limits more efficiently using these new approximation algorithms.
  • For urban infrastructure teams: Plan utility or transport networks in city layouts modeled as planar graphs with guaranteed near-optimal cost and limited path length overrun.

Authors

D Ellis Hershkowitz, Richard Z Huang, Rhea Jain, Manas Korimilli

Abstract

Problems in length-constrained network design ask for min-cost subgraphs connecting $k$ input vertex pairs by paths of length at most $h$. Algorithms that instead connect these pairs by paths of length at most $βh$ are said to have length slack $β$. Recent work has shown that poly-time polylogarithmic approximations with polylogarithmic length slack are possible for a broad class of both directed and multicommodity length-constrained network design problems on planar graphs. We give the first poly-time polylogarithmic approximations with $O(1)$ length slack for these problems on planar graphs. In particular, for the length-constrained setting, we give LP-competitive algorithms for planar graphs with length slack $1+ε$ and approximation ratios of $O(\log^2 k/ε)$ for directed Steiner tree and $O(\log^5 k/ε^2)$ for (undirected) Steiner forest. Similarly, for length-constrained directed Steiner forest, we give an $O(\log^6 k/ε)$ approximation on planar graphs with length slack $6+ε$. Our approach is based on a novel charging argument that charges the cost of our solution to the length of the LP and the length of our solution to the cost of the LP. We complement these algorithms with hardness results that separate planar and general graphs for both forest problems: under standard complexity assumptions, we rule out polylogarithmic approximations on general graphs with length slack below $3$.