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]

Given a k -coloring of a graph G , a Kempe-change for two colors a and b produces another k -coloring of G , as follows: first choose a connected component in the subgraph of G induced by the two color classes of a and b , and then swap the colors a and b in the component. Two k -colorings are called Kempe-equivalent if one can be transformed into the other by a sequence of Kempe-changes. We consider two problems, defined as follows: First, given two k -colorings of a graph G , Kempe Reachability asks whether they are Kempe-equivalent; and second, given a graph G and a positive integer k , Kempe Connectivity asks whether any two k -colorings of G are Kempe-equivalent. We analyze the complexity of these problems from the viewpoint of graph classes. We prove that Kempe Reachability is PSPACE -complete for any fixed k ≥ 3 , and that it remains PSPACE -complete even when restricted to three colors and planar graphs of maximum degree six. Furthermore, we show that both problems admit polynomial-time algorithms on chordal graphs, bipartite graphs, and cographs. For each of these graph classes, we give a non-trivial upper bound on the number of Kempe-changes needed in order to certify that two k -colorings are Kempe-equivalent. [ABSTRACT FROM AUTHOR]