论文标题
关于双重跨越树问题的复杂性
On the Complexity of the Bilevel Minimum Spanning Tree Problem
论文作者
论文摘要
我们考虑双重最小生成树（BMST）问题，其中领导者和追随者根据不同的目标函数选择一个生成树。通过证明这个问题通常是NP危害，我们回答了Shi等人所说的一个空旷的问题。我们证明，即使在追随者只能控制匹配的特殊情况下，BMST仍然很难。此外，通过从顶点 - 偶发者施泰纳树问题中的多项式减少，我们提供了一些证据，表明BMST甚至可能仍然很难，以防自动机控制只有很少的边缘。从积极的一面来看，我们提供了一个多项式$（| v | -1）$ - BMST的近似算法，其中$ | v | $是输入图中的顶点数量。此外，考虑到追随者控制的边缘数量作为参数，我们表明2-抗Ximating BMST是固定参数可进行的，并且在领导者边缘上的统一成本中，即使求解BMST的确切求解也是固定参数的固定参数。我们最终考虑了BMST的瓶颈变体，并解决了领导者和追随者的所有总和或瓶颈目标函数的复杂性景观，以使其乐观和悲观的环境。
We consider the bilevel minimum spanning tree (BMST) problem where the leader and the follower choose a spanning tree together, according to different objective functions. By showing that this problem is NP-hard in general, we answer an open question stated in by Shi et al. We prove that BMST remains hard even in the special case where the follower only controls a matching. Moreover, by a polynomial reduction from the vertex-disjoint Steiner trees problem, we give some evidence that BMST might even remain hard in case the follower controls only few edges. On the positive side, we present a polynomial-time $(|V|-1)$-approximation algorithm for BMST, where $|V|$ is the number of vertices in the input graph. Moreover, considering the number of edges controlled by the follower as parameter, we show that 2-approximating BMST is fixed-parameter tractable and that, in case of uniform costs on leader's edges, even solving BMST exactly is fixed-parameter tractable. We finally consider bottleneck variants of BMST and settle the complexity landscape of all combinations of sum or bottleneck objective functions for the leader and follower, for the optimistic as well as the pessimistic setting.
