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

摘要

Singleton attractor (also called fixed point) detection is known to be NP-hard even for AND/OR Boolean networks (AND/OR BNs in short, i.e., BNs consisting of AND/OR nodes), where BN is a mathematical model of genetic networks and singleton attractors correspond to steady states. In our recent paper, we developed an O(1.787 n ) 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.757 n ) time algorithm with which we succeeded in improving the above algorithm. We also show that this problem can be solved in $2^{O(({rm log} , n)sqrt{n})}$ time, which is less than O((1 + ∈) n ) for any positive constant ∈, when a BN is planar.