Parameter limits revealed for graph spanner problems with varied weights
Parameterized Complexity of Spanner Problems with Independent Weights and Lengths
Data Structures and Algorithms
Summary
This paper looks at a problem in computer science where you try to simplify a network by keeping important paths short but with different weights and lengths on connections. The authors find that many ways of measuring the problem are too hard to solve efficiently, but they also develop new methods that work better when considering the total weight of removed connections and a new tighter measure than the usual one. These findings improve earlier results for simpler cases and identify when the problem gets much harder or easier based on what you measure.
What this means in practice
- •For network schedulers: Design better scheduling systems by understanding which network simplifications are computationally feasible when using weights and lengths on connections.
- •For transportation planners: Use new complexity results to evaluate realistic route simplifications in transportation networks with varying travel times and costs.
A theory result. No direct application yet.
Authors
Marius Bächler, Markus Chimani, Henning Jasper
Abstract
In this paper, the parameterized complexity of the multiplicative $α$-spanner problem with independent weights and lengths on undirected graphs is considered for the first time. All prior FPT results (except one on DAGs) assume basic instances (i.e., with unit weights and lengths) and are parameterized in the stretch factor $α$ and the (in practice typically non-constant) number of removed edges. We show that several parameterizations do not allow FPT algorithms. However, our exclusion approach generalizes an existing algorithm for basic instances to arbitrary weights and lengths. It is parameterized by the total removed weight and a new tightness parameter. The latter is more precise than $α$ and allows us to also improve the best known result for basic instances. Our second algorithm, called inclusion approach, uses the natural parameterization in the spanner's total weight. We prove that this sole parameter leaves a W[2]-hard problem, but also show FPT algorithms exist when augmented with secondary parameters.