A computational study of f-reversible processes on graphs

An f-reversible process on a graph G=(V,E) is a graph dynamical system on V(G) defined as follows. Given a function f:V(G)→N and an initial vertex labeling c0:V(G)→{0,1}, every vertex v changes its label if and only if at least f(v) of its neighbors have the opposite state, synchronously in discrete-time. For such processes, we present a new nondecreasing time function similar to the monotonically decreasing energy functions used to study threshold networks, which leads to a periodic behavior after a transient phase. Using this new function, we provide a tight upper bound on the transient length of f-reversible processes. Furthermore, we prove that it is equal to n−3 for trees with n≥4 vertices and Im(f)={2}. Moreover we present an algorithm that generates all the initial configurations attaining this bound and we prove that the number of such configurations is O(n). We also consider the problem of determining the smallest number rf(G) of vertices with initial label 1 for which all the vertices eventually reach label 1 after the complete evolution of the dynamics, which models consensus problems on networks. We prove that it is NP-hard to compute rf(G) even for bipartite graphs with Δ(G)≤3 and Im(f)={1,2,3}. Finally, we prove that β(G)≤rf(G)≤β(G)+1, when f(v)=d(v) for all v∈V(G), where β(G) is the size of a minimum vertex cover of G.