标题： 带有受限链路使用的同步网络设计 显示英文标题

标题： Simultaneous Network Design with Restricted Link Usage

摘要： 给定一个具有两个终端顶点$s$和$t$的有向图，以及一个保守的成本函数和其边集上的若干不一定不相交的颜色类，我们的目标是找到边的一个最小成本子集，使得其与每个颜色类的交集包含一个$s$-$t$有向路径。 这类问题在多商品网络设计环境中自然出现，其中每个商品仅被限制使用其自身颜色的链路。 我们研究了该问题的几个变种，即使在受限情况下也得出了强大的难解性结果，但我们同时也识别出了一些可以在多项式时间内求解的情况。 后者包括颜色类形成层叠族的情况，或者基础有向图是无环的且颜色类的数量是常数的情况。 我们还提出了一个针对一般情况的FPT算法，参数为多色边的数量。 显示英文摘要

摘要： Given a digraph with two terminal vertices $s$ and $t$ as well as a conservative cost function and several not necessarily disjoint color classes on its arc set, our goal is to find a minimum-cost subset of the arcs such that its intersection with each color class contains an $s$-$t$ dipath. Problems of this type arise naturally in multi-commodity network design settings where each commodity is restricted to use links of its own color only. We study several variants of the problem, deriving strong hardness results even for restricted cases, but we also identify cases that can be solved in polynomial time. The latter ones include the cases where the color classes form a laminar family, or where the underlying digraph is acyclic and the number of color classes is constant. We also present an FPT algorithm for the general case parameterized by the number of multi-colored arcs.