2015/08/06 by Mühlenthaler, Moritz
#05C40 (secondary) #05C70 #68R10 (primary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.1508.01372
The degree-constrained subgraph problem asks for a subgraph of a given graph such that the degree of each vertex is within some specified bounds. We study the following reconfiguration variant of this problem: Given two solutions to a degree-constrained subgraph instance, can we transform one solution into the other by adding and removing individual edges, such that each intermediate subgraph satisfies the degree constraints and contains at least a certain minimum number of edges? This problem is a generalization of the matching reconfiguration problem, which is known to be in P. We show that even in the more general setting the reconfiguration problem is in P.