Robust matchings and matroid intersections
Robust matchings and matroid intersections
复制标题
稳健匹配和拟阵交集
DOI：
10.1137/100808800
复制
发表时间：
2013
影响因子：
0.8
通讯作者：
and K. Makino
中科院分区：
文献类型：
--
作者：
R. Fujita;Y. Kobayashi;and K. Makino
在一个加权独立系统中，如果一个独立集的所有权元素的总权至少是一个独立集的最大权的倍，则称该独立集是鲁棒的。这里的独立集是指具有最多元素的独立集。加权图中的匹配集是加权独立系统的典型示例，并且Hassin和Rubinstein [SIAM J. Discrete Math.，15（2002），pp. 530- 537]证明了每个图都有a-鲁棒匹配，并且可以用ath幂算法在多项式时间内找到。在本文中，我们表明，它可以扩展到拟阵相交问题，即，总是存在一个鲁棒拟阵交，它是多项式可计算的。我们还研究了鲁棒匹配问题的时间复杂度。我们证明了1-鲁棒匹配可以在多项式时间内计算（如果存在的话），并且，对于任何固定的数，确定给定的加权图是否有一个-鲁棒匹配的问题是NP-完全的。这些结果与[R. Hassin和S. Rubinstein，SIAM J.离散数学，15（2002），pp. 530- 537]给出了鲁棒匹配问题的复杂性的清晰边界。此外，我们还证明了当是输入的一部分时，该问题是强NP完全的。最后，我们展示了用于鲁棒匹配的次幂算法的局限性;即，对于任何一个，存在一个加权图，使得非幂算法输出用于计算最鲁棒匹配的近似。
In a weighted independence system, an independent set is said to be-robust if, for all, the total weight of its heaviestelements is at leasttimes the maximum weight of a-independent set. Here a-independent set is an independent set with at mostelements. The set of matchings in a weighted graph is a typical example of a weighted independence system, and Hassin and Rubinstein [SIAM J. Discrete Math., 15 (2002), pp. 530--537] showed that every graph has a-robust matching and it can be found by ath power algorithm in polynomial time. In this paper, we show that it can be extended to the matroid intersection problem; i.e., there always exists a-robust matroid intersection, which is polynomially computable. We also study the time complexity of the robust matching problem. We show that a 1-robust matching can be computed in polynomial time (if one exists), and, for any fixed numberwith, the problem to determine whether a given weighted graph has an-robust matching is NP-complete. These together with the positive result forin [R. Hassin and S. Rubinstein,SIAM J. Discrete Math., 15 (2002), pp. 530--537] give us a sharp border for the complexity for the robust matching problem. Moreover, we show that the problem is strongly NP-complete whenis a part of the input. Finally, we show the limitations of theth power algorithm for robust matchings; i.e., for any, there exists a weighted graph such that noth power algorithm outputs a-approximation for computing the most robust matching.