Compatible 2-factors (Q1193724): Difference between revisions

A 2-factor of a graph \(G\) is a spanning subgraph \(F\) of \(G\) in which each vertex has degree 2. The pair of edges of \(F\) incident with a vertex \(v\) is called a transition of \(F\) at \(v\). Suppose at each vertex \(v\) of \(G\) we are given a set \(T(v)\) of allowed transitions (pairs of edges incident with \(v)\); a compatible 2-factor is one in which the transition at each \(v\) is from the corresponding set \(T(v)\). The authors study the question of deciding, for a given graph \(G\) with a transition system \(T\), whether or not there is a compatible 2-factor. Each set \(T(v)\) can be viewed as a graph whose vertices are the edges incident on \(v\). The authors give a polynomial algorithm to decide the existence of compatible 2-factors in two special situations: (1) when each \(T(v)\) is a complete multipartite graph (with possibly some isolated vertices); and (2) when each \(T(v)\) is a subgraph of a four-cycle (again with possibly some isolated vertices). Case (1) is solved essentially by reduction to matching, and case (2) by reduction to 2-satisfiability. The authors also show that in all other situations the problems are NP-complete.