Search

We study the complexity of deciding whether for two given feedback vertex sets of a graph there is a step-by-step transformation between them, such that for each feedback vertex set in the transformation, the next one is obtained by exchanging a single vertex. We give a classification of the complexity of this question for planar graphs in terms of the maximum degree. We show that for planar graphs of maximum degree at most three the problem is tractable because there always exists a transformation, while it is PSPACE -complete when the maximum degree is at most four. The positive side of the classification extends to K 3 , 3 -minor-free graphs of maximum degree three. We then consider the Matroid Parity problem, which generalizes feedback vertex sets in graphs of maximum degree three as well as matchings and spanning trees in general graphs. Generalizing known results for the latter two we show that there always exists a transformation between any two non-maximum independent parity sets. [ABSTRACT FROM AUTHOR]

Subgraph reconfiguration is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertices or sets of edges, satisfying a prescribed graph structure property. Although there has been previous work that can be categorized as subgraph reconfiguration , most of the related results appear under the name of the property under consideration; for example, independent set, clique, and matching. In this paper, we systematically clarify the complexity status of subgraph reconfiguration with respect to graph structure properties. [ABSTRACT FROM AUTHOR]