在本研究中，我们探讨了受电力网络设计启发的Steiner树问题的广义化。传统的Steiner树问题关注的是连接给定终端顶点的单一最小成本树，而电力网络通常由多个树构成，每棵树连接一部分终端以避免电力过载。
安装成本不仅取决于电缆长度，还取决于挖掘地下沟渠的成本，而这些沟渠的挖掘成本可以共享。这导致了Steiner树的变种，目标是计算一组具有共同根节点的最小成本Steiner树，以便在每棵树中平衡终端的电力需求并连接所有终端。
根据网络是低压还是高压电力，两种重要的变种应运而生。在低压情况下，电力损失限制了每棵树的最大深度，而在高压情况下则没有这样的限制。
我们研究了几个电力网络设计问题的参数化复杂性，这些问题以终端数量为参数。虽然在此参数化下，Steiner树是固定参数可解的，但我们的大多数变种都是W[1]-困难的。
对于低压网络，我们提出了一种基于解子图树宽的结构界限的平面输入的XP算法。同时，我们还给出了来自网格铺设的归约，显示了在ETH下的紧致性。该XP算法可以扩展到高压设置和一般图，但运行时间有所增加。
对于高压网络，我们证明该问题即使在平面图上仍然是W[1]-困难的。最后，我们探讨了一种共享挖掘成本的成本模型变种，使得两个问题都变为固定参数可解。
博主点评： 本文深入探讨了电力网络设计中的复杂性，尤其是在协调电缆布置方面的挑战。通过对不同电压情况下问题的分析，提供了有效的算法和理论支持，展示了参数化复杂性在实际应用中的重要性。