Title: A Polynomial-Time Algorithm for Solving the Minimal Observability Problem in Conjunctive Boolean Networks,
Abstract: Many complex systems in biology, physics, and engineering include a large
number of state-variables, and measuring the full state of the system is often
impossible. Typically, a set of sensors is used to measure part of the
state-variables. A system is called observable if these measurements allow to
reconstruct the entire state of the system. When the system is not observable,
an important and practical problem is how to add a \emph{minimal} number of
sensors so that the system becomes observable. This minimal observability
problem is practically useful and theoretically interesting, as it pinpoints
the most informative nodes in the system. We consider the minimal observability
problem for an important special class of Boolean networks, called conjunctive
Boolean networks (CBNs). Using a graph-theoretic approach, we provide a
necessary and sufficient condition for observability of a CBN with $n$
state-variables, and an efficient~$O(n^2)$-time algorithm for solving the
minimal observability problem. We demonstrate the usefulness of these results
by studying the properties of a class of random CBNs.