On the Complexity of Partitioning Graphs for Arc-Flags

Precomputation of auxiliary data in an additional off-line step is a common approach towardsimproving the performance of shortest-path queries in large-scale networks. One such techniqueis the arc-flags algorithm, where the preprocessing involves computing a partition of the inputgraph. The quality of this partition significantly affects the speed-up observed in the queryphase. It is evaluated by considering the search-space size of subsequent shortest-path queries, inparticular its maximum or its average over all queries. In this paper, we substantially strengthenexisting hardness results of Bauer et al. and show that optimally filling this degree of freedomis NP-hard for trees with unit-length edges, even if we bound the height or the degree. Onthe other hand, we show that optimal partitions for paths can be computed efficiently and giveapproximation algorithms for cycles and trees.