Reconfiguration of maximum-weight b-matchings in a graph
Reconfiguration of maximum-weight b-matchings in a graph
复制标题
图中最大权重 b 匹配的重新配置
DOI：
10.1007/s10878-018-0289-3
复制
发表时间：
2018
影响因子：
1
通讯作者：
and Yoshio Okamoto
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;and Yoshio Okamoto
考虑一个图，使得每个顶点都有非负整数容量，每条边都有正整数权重。然后，图中的ab-匹配是一个多组边（由边上的整数向量表示），使得与每个顶点关联的边的总数至多是该顶点的容量。在本文中，我们研究了最大权b-匹配的一个重构变体：对于图中的两个给定的最大权b-匹配，我们被要求确定是否存在一个序列的最大权b-匹配之间的图中，通过删除一个边缘和添加另一个获得的最大权b-匹配。我们表明，这个重新配置问题是可解的，在多项式时间的情况下，没有完整性差距。这样的例子包括在顶点上具有任何容量函数的二部图，以及一般图中的2-匹配。因此，我们的结果意味着最大权匹配的重新配置问题可以在多项式时间内解决二分图。
Consider a graph such that each vertex has a nonnegative integer capacity and each edge has a positive integer weight. Then, ab-matching in the graph is a multi-set of edges (represented by an integer vector on edges) such that the total number of edges incident to each vertex is at most the capacity of the vertex. In this paper, we study a reconfiguration variant for maximum-weightb-matchings: For two given maximum-weightb-matchings in a graph, we are asked to determine whether there exists a sequence of maximum-weightb-matchings in the graph between them, with subsequentb-matchings obtained by removing one edge and adding another. We show that this reconfiguration problem is solvable in polynomial time for instances with no integrality gap. Such instances include bipartite graphs with any capacity function on vertices, and 2-matchings in general graphs. Thus, our result implies that the reconfiguration problem for maximum-weight matchings can be solved in polynomial time for bipartite graphs.