Given a (di)graph G and a threshold function \(f:V(G) \rightarrow \mathbb {N}\) , an f-reversible process on G is a dynamical system such that, given an initial vertex labeling \(c_0: V(G) \rightarrow \{0,1\}\) , every vertex v changes its label if and only if it has at least f(v) neighbors (or in-neighbors when G is a digraph) with the opposite label, synchronously in discrete-time steps. An f-conversion set of G is a subset of vertices of G with initial label equal to 1 such that, in an f-reversible process on G, there is a time step \(t \ge 0\) in which all vertices have label 1 from there on, and an f-critical set of G is an f-conversion set of G in which this time t is 0 or 1. When f is constant, we can change the f for that constant in this notations. In this work, we show that we can find a smallest 1-conversion set of a tournament and a smallest f-critical set of a path in linear time. On the negative side, we show that the problem of determining if there is a 1-conversion set with size at most k is NP-hard for digraphs with only one cycle and in which each vertex has the sum of its in-degree and out-degree at most three.
