Period Piece: NEXPTIME-complete problems on digraphs via Boolean network dynamics

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 $\phi$, we say that a digraph $G$ is $\phi$-dynamic if $G$ is the interaction graph of some Boolean network $f$ such that $D_f\models \phi$. The corresponding decision problem $\phi$-DYNAMIC asks whether $G$ is $\phi$-dynamic. Problems of this form are well-studied in the Boolean networks community. For example, it is a well-known result that, letting $\phi$ be ‘No fixed points’ (i.e. $\mathrm{\nexists }x:x\to x$), $\phi$-DYNAMIC is equivalent to the structural digraph problem NON-ACYCLIC, which is solvable in linear time. We establish, for the first time, properties $\phi$ for which $\phi$-DYNAMIC is computationally hard. These include the ‘Unique fixed point’ property $\mathrm{\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 $\phi$ such that $\phi$-DYNAMIC is $\mathrm{N}\mathrm{E}\mathrm{X}\mathrm{P}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}$-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 $\phi$-DYNAMIC collapses down to ${\mathrm{N}\mathrm{P}}^{\mathrm{N}\mathrm{P}}$, the second level of the polynomial hierarchy, though it remains ${\mathrm{N}\mathrm{P}}^{\mathrm{N}\mathrm{P}}$-complete.