Algorithms for Singleton Attractor Detection in Planar and Nonplanar AND/OR Boolean Networks

Abstract

Singleton attractor (also called fixed point) detection is known to be NP-hard even for AND/OR BNs (i.e., BNs consisting of AND/OR nodes), where the Boolean network (BN) is a mathematical model of genetic networks and singleton attractors correspond to steady states. In our recent paper, we developed an O(1:787n) time algorithm for detecting a singleton attractor of a given AND/OR BN where n is the number of nodes. In this paper, we present an O(1:757n) time algorithm with which we succeeded in improving the above algorithm. We also show that this problem can be solved in O((1 + ²)n) time when a BN is planar, where ² is any positive constant.