TY - JOUR
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:
Takehiro Ito was supported by JST CREST Grant Number JPMJCR1402, and by JSPS KAKENHI Grant Number JP16K00004, Japan. Naonori Kakimura was supported by JST ERATO Grant Number JPMJER1201, and by JSPS KAKENHI Grant Number JP17K00028, Japan. Naoyuki Kamiyama was supported by JST PRESTO Grant Number JPMJPR14E1, Japan. Yusuke Kobayashi was supported by JST ERATO Grant Number JPMJER1201, and by JSPS KAKENHI Grant Numbers JP16K16010 and JP16H03118, Japan. Yoshio Okamoto was supported by Kayamori Foundation of Informational Science Advancement, JST CREST Grant Number JPMJCR1402, and JSPS KAKENHI Grant Numbers JP24106005, JP24700008, JP24220003 and JP15K00009, Japan.
Publisher Copyright:
© 2018, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2019/2/15
Y1 - 2019/2/15
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.
KW - Combinatorial reconfiguration
KW - Graph algorithm
KW - b-matching
UR - http://www.scopus.com/inward/record.url?scp=85046039917&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85046039917&partnerID=8YFLogxK
U2 - 10.1007/s10878-018-0289-3
DO - 10.1007/s10878-018-0289-3
M3 - Article
AN - SCOPUS:85046039917
SN - 1382-6905
VL - 37
SP - 454
EP - 464
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 2
ER -