The complexity of the evolution of GRAPH LABELINGS

Abstract

We study the GRAPH RELABELING PROBLEM-given an undirected, connected, simple graph G = (V, E), two labelings l and l′ of G, and label mutation or flip functions determine the complexity of evolving the labeling l into l′. The transformation of l into l′ can be viewed as an evolutionary process governed by the types of mutations or flips allowed. The number of applications of the function is the duration of the evolutionary period. The labels may reside on the vertices or the edges. We prove that vertex and edge relabeling have closely related computational complexities. Upper and lower bounds on the number of imitations required to evolve one labeling into another in a general graph are given. We also explore both vertex and edge relabeling with privileged labels, and resolve some open problems by providing precise characterizations of when these problems are solvable. Many of our results include algorithms for solving the problems, and in all cases the algorithms are polynomial-time. The problems studied have applications in areas such as bioinformatics, networks, and VLSI. © 2008 IEEE.