在 Steiner 树问题中，给定一张带权无向图和一组终端点，目标是找到一棵最小权值的树，使所有终端点都被包含。若已知一个大小为 $s$ 的多路割（即删除该集合后，每个连通分量至多包含一个终端），本文给出一种确定性算法，时间复杂度为 $2^{O(s)}\operatorname{poly}(n,b)$，空间为多项式级（其中 $n$ 为顶点数，$b$ 为权值的比特数）。
多路割的定义：对终端集合 $T$，若 $C\subseteq V$ 满足 $G\setminus C$ 的每个连通分量至多包含 $T$ 中的一个顶点，则 $C$ 为 $T$ 的多路割。该概念在 Jansen 与 Swennenhuis (ESA 2024) 的工作中被提出，本文的结果直接回答了他们提出的开放问题。
核心思路基于他们的组件分解：先将图划分为若干组件，每个组件内部至多含一个终端。随后只需在割点集合中选取若干额外的 $O(s)$ 个“伪终端”，并将这些点与原始终端通过最短路径相连，即可构造出满足 Steiner 条件的树。关键在于如何挑选这 $O(s)$ 个伪终端，本文采用颜色编码（colour coding）技术，对所有可能的选择进行指数级但可控的枚举，从而实现单指数时间。
算法流程概括如下：
- 给定多路割 $C$，计算每个割点到所有终端的最短路径长度。
- 使用颜色编码为每个割点分配颜色，枚举所有颜色组合对应的 $O(s)$ 伪终端集合。
- 对每个组合，构造包含割点、伪终端以及原始终端的最短路径子图，并检查其是否形成连通的 Steiner 树。
- 记录权值最小的合法解，即为所求的最优 Steiner 树。
该算法仅使用多项式空间，因为所有中间结构均可在 $O(n)$ 空间内维护，且颜色编码的动态规划表也只需 $2^{O(s)}$ 大小。
点评：本文在 Steiner 树的参数化复杂度上取得突破，将多路割大小作为参数，实现了单指数时间且保持多项式空间，展示了颜色编码在图结构优化中的强大潜力。