{"id":"arxiv/2610.16561","url":"https://arxiv.org/abs/2610.16561","tags":["cs.DM","cs.CC","math.CO"],"score":0,"title":"Period Piece: NEXPTIME-complete problems on digraphs via Boolean network dynamics","domain":"cs.DM","source":"arxiv","authors":["Florian Bridoux","Maximilien Gadouleau","David C. Kutner","Adrien Richard"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}