Summary
This paper studies Boolean networks, which are like switches connected by wires showing how pieces depend on each other. The authors look at how hard it is to decide if a network’s structure can produce certain behaviors, like having one unique stable state or specific kinds of repeating patterns. They show that some of these questions become extremely complex, much harder to solve than previously known. However, if the network is limited so each node listens to only a few nodes, the complexity decreases but still stays challenging. This helps us understand which dynamic properties are computationally difficult to predict from the network’s wiring.
What this means in practice
- •For graph algorithm designers: Guide designing algorithms by ruling out efficient solutions for finding unique fixed points or specific cycles in network dynamics without degree bounds.
- •For systems engineers: Inform system modeling by indicating that verifying some dynamic properties in bounded-degree networks remains computationally demanding at a high complexity level.
A theory result. No direct application yet.
Authors
Florian Bridoux, Maximilien Gadouleau, David C. Kutner, Adrien Richard
Abstract
The central object in this work is the Boolean network, a function $f:\{0,1\}^V \to \{0,1\}^V$. Often identified with $f$ is its dynamics $D_f$, the digraph with exactly $\{x \to y : f(x)=y\}$ as its arcs. The interaction graph of $f$ is the digraph $G$ on $V$ which can be thought of as representing the dependencies of the components of $f$ on one another. On the other hand, model-checking is a major field of study in graph algorithms and complexity. We consider problems at the intersection of these paradigms: for a given property $φ$, we say that a digraph $G$ is $φ$-dynamic if $G$ is the interaction graph of some Boolean network $f$ such that $D_f \models φ$. The corresponding decision problem $φ$-DYNAMIC asks whether $G$ is $φ$-dynamic. Problems of this form are well-studied in the Boolean networks community. For example, it is a well-known result that, letting $φ$ be 'No fixed points' (i.e. $\nexists x:x\to x$), $φ$-DYNAMIC is equivalent to the structural digraph problem NON-ACYCLIC, which is solvable in linear time. We establish, for the first time, properties $φ$ for which $φ$-DYNAMIC is computationally hard. These include the 'Unique fixed point' property $\exists!x:x\to x$, and a range of properties concerning the periodic points of $f$ (i.e. vertices of $D_f$ which lie on a cycle). More widely, we exhibit an infinite family of natural properties $φ$ such that $φ$-DYNAMIC is $\mathrm{NEXPTIME}$-complete, which we call PERIOD PIECE. As a special case, these include all properties of the form 'Unique cycle of length $k$' and 'Exactly $k$ fixed points' for any $k \ge 1$. On the other hand, we show that if the input digraph has bounded in-degree, then for those same problems $φ$-DYNAMIC collapses down to $\mathrm{NP}^{\mathrm{NP}}$, the second level of the polynomial hierarchy, though it remains $\mathrm{NP}^{\mathrm{NP}}$-complete.