Prof. Avraham Melkman

Although it is in general NP-hard to find a singleton attractor of a sign-definite network, if the network is strongly connected and has no directed negative cycle then it has at least two singleton attractors that can be found in polynomial time, as proved by Aracena. We describe an algorithm for finding a singleton attractor of a sign-definite network which does not have a directed negative cycle but is not necessarily strongly connected. The algorithm is not only much simpler than the algorithm of Goles and Salinas for the same problem, but also, unlike their algorithm, runs in polynomial time. It was proven by Just that the problem of finding a 2-periodic attractor is in a sense harder yet, because it remains NP-hard for a positive network. We prove, however, that if the positive network has a source strongly connected component devoid of odd cycles, then it is possible to find a 2-periodic attractor in polynomial-time, and we present an algorithm for doing so.