This study explores generalizations of the Steiner Tree problem motivated by power network design. While the Steiner Tree asks for a single minimum-cost tree connecting given terminal vertices, a power network typically consists of multiple trees, each connecting a subset of the terminals to avoid electrical overloads.
The cost of installation depends on both cable lengths and the cost of digging underground trenches, which can be shared. This leads to variants of the Steiner Tree where the goal is to compute a minimum-cost set of Steiner trees with a common root, connecting all terminals while balancing their power demand.
Two important variants arise depending on whether the network is for low-voltage or high-voltage power. In the low-voltage case, power loss limits the maximum depth of each tree, while no such restriction applies in the high-voltage case.
We study the parameterized complexity of several power network design problems, parameterized by the number of terminals. While the Steiner Tree remains fixed-parameter tractable under this parameterization, most of our variants are W[1]-hard.
For low-voltage networks, we present an XP-algorithm for planar inputs based on structural bounds on the treewidth of solution subgraphs. We also provide a reduction from Grid Tiling showing tightness under ETH. The XP-algorithm extends to the high-voltage setting and general graphs, albeit with increased running time.
For high-voltage networks, we show the problem remains W[1]-hard even on planar graphs. Finally, we explore a variant of the cost model for sharing digging costs in which both problems become fixed-parameter tractable.
Blogger's Review: This article delves into the complexities of power network design, especially the challenges in coordinating cable placements. By analyzing the problems under different voltage scenarios, it provides effective algorithms and theoretical support, highlighting the importance of parameterized complexity in practical applications.