NAC-coloring search: complexity and algorithms

One of the questions in Rigidity Theory is whether a realization of the vertices of a graph in the plane is flexible, namely, if it allows a continuous deformation preserving the edge lengths. A flexible realization of a connected graph in the plane exists if and only if the graph has a NAC-coloring, which is surjective edge coloring by two colors such that for each cycle either all the edges have the same color or there are at least two edges of each color. While it is known that it is NP-complete to decide if a graph has a NAC-coloring, we show that the problem is also NP-complete for graphs with maximum degree five. We present a significantly faster algorithm with an implementation for NAC-coloring search, and we discuss related heuristics. The performance is compared with previous algorithms and among the heuristics. We also present fixed-parameter tractable (FPT) algorithm for NAC-coloring counting parametrized by treewidth. We discuss relation to stable cuts and an algorithm for finding a stable cut is implemented as part of the thesis.