TY - GEN
T1 - Reconfiguration of maximum-weight b-matchings in a graph
AU - Ito, Takehiro
AU - Kakimura, Naonori
AU - Kamiyama, Naoyuki
AU - Kobayashi, Yusuke
AU - Okamoto, Yoshio
N1 - Funding Information:
T. Ito – Supported by JST CREST Grant Number JPMJCR1402, Japan, and JSPS KAKENHI Grant Number JP16K00004. N. Kakimura – Supported by JST ERATO Grant Number JPMJER1305, Japan, and by JSPS KAKENHI Grant Number JP17K00028. N. Kamiyama – Supported by JST PRESTO Grant Number JPMJPR14E1, Japan. Y. Kobayashi – Supported by JST ERATO Grant Number JPMJER1305, Japan, and by JSPS KAKENHI Grant Numbers JP16K16010 and JP16H03118. Y. Okamoto – Supported by Kayamori Foundation of Informational Science Advancement, JST CREST Grant Number JPMJCR1402, Japan, and JSPS KAK-ENHI Grant Numbers JP24106005, JP24700008, JP24220003, JP15K00009.
Publisher Copyright:
© 2017, Springer International Publishing AG.
PY - 2017
Y1 - 2017
N2 - Consider a graph such that each vertex has a nonnegative integer capacity and each edge has a positive integer weight. Then, a b-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-weight b-matchings: For two given maximum-weight b-matchings in a graph, we are asked to determine whether there exists a sequence of maximum-weight b-matchings in the graph between them, with subsequent b-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.
AB - Consider a graph such that each vertex has a nonnegative integer capacity and each edge has a positive integer weight. Then, a b-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-weight b-matchings: For two given maximum-weight b-matchings in a graph, we are asked to determine whether there exists a sequence of maximum-weight b-matchings in the graph between them, with subsequent b-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.
UR - http://www.scopus.com/inward/record.url?scp=85028448554&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028448554&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-62389-4_24
DO - 10.1007/978-3-319-62389-4_24
M3 - Conference contribution
AN - SCOPUS:85028448554
SN - 9783319623887
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 287
EP - 296
BT - Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings
A2 - Cao, Yixin
A2 - Chen, Jianer
PB - Springer Verlag
T2 - 23rd International Conference on Computing and Combinatorics, COCOON 2017
Y2 - 3 August 2017 through 5 August 2017
ER -