Linear Algorithm for a Cyclic Graph Transformation

Resumo

We propose a linear time and linear space algorithm that constructs a minimal (in the total cost) sequence of operations required to transform a directed graph consisting of disjoint cycles into any graph of the same type. The following operations are allowed: double-cut-and-join of vertices and insertion or deletion of a connected fragment of edges; the latter two operations have the same cost. We present a complete proof that the algorithm finds the corresponding minimum. The problem is a nontrivial particular case of the general problem of transforming a graph into another, which in turn is an instance of a hard optimization problem in graphs. In this general problem, which is known to be NP-complete, each vertex of a graph is of degree 1 or 2, edges with the same name may repeat unlimitedly, and operations belong to a well-known list including the above-mentioned operations. We describe our results for the general problem, but the proof is given for the cyclic case only.