标题： 强制一个唯一的最小生成树和一个唯一的最短路径 显示英文标题

标题： Forcing a unique minimum spanning tree and a unique shortest path

摘要： 在组合问题中的强制集$S$是一个元素集合，使得存在一个唯一包含$S$中所有元素的解。 反强制集是对称概念：一个元素集合$S$被称为反强制集，如果存在一个与$S$不相交的唯一解。 关于在各种组合问题中寻找最小强制集的计算复杂性有大量研究，已知结果表明许多问题比其经典对应问题更难：寻找完美匹配的最小强制集是 NP-难的 [Adams 等，Discret. Math. 2004]，寻找 3CNF 公式的满足赋值的最小强制集是$\mathrm{\Sigma}_2^P$-难的 [Hatami-Maserrat, DAM 2005]。 在本文中，我们研究了寻找最短$s$-$t$路径问题和最小权生成树问题的最小强制集和反强制集问题的复杂性。 我们证明，与上述结果不同，这些问题是易处理的，除了寻找最短$s$-$t$路径的最小反强制集以外，这是NP难的。 显示英文摘要

摘要： A forcing set $S$ in a combinatorial problem is a set of elements such that there is a unique solution that contains all the elements in $S$. An anti-forcing set is the symmetric concept: a set $S$ of elements is called an anti-forcing set if there is a unique solution disjoint from $S$. There are extensive studies on the computational complexity of finding a minimum forcing set in various combinatorial problems, and the known results indicate that many problems would be harder than their classical counterparts: finding a minimum forcing set for perfect matchings is NP-hard [Adams et al., Discret. Math. 2004] and finding a minimum forcing set for satisfying assignments for 3CNF formulas is $\mathrm{\Sigma}_2^P$-hard [Hatami-Maserrat, DAM 2005]. In this paper, we investigate the complexity of the problems of finding minimum forcing and anti-forcing sets for the shortest $s$-$t$ path problem and the minimum weight spanning tree problem. We show that, unlike the aforementioned results, these problems are tractable, with the exception of finding a minimum anti-forcing set for shortest $s$-$t$ paths, which is NP-hard.