Period Piece: NEXPTIME-complete problems on digraphs via Boolean network dynamics
Abstract
The central object in this work is the Boolean network, a function f:{0,1}V → {0,1}V. Often identified with f is its dynamics Df, the digraph with exactly {x → 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 Df ⊨ ϕ. 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→ 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 ∃!x:x→ x, and a range of properties concerning the periodic points of f (i.e. vertices of Df which lie on a cycle). More widely, we exhibit an infinite family of natural properties ϕ such that ϕ-DYNAMIC is 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 ≥ 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 NPNP, the second level of the polynomial hierarchy, though it remains NPNP-complete.
Related
- Hyperstructures as complete atomic Boolean algebras
- An FPT algorithm for cycle rank on semi-complete digraphs
- Construction of New Complete Complementary Codes Using Extended Boolean Functions and Permutations
- Avalanche homology of digraphs via sandpile dynamics
- Karp's NP-complete problems over first-order definable structures
BibTeX
@misc{bridoux2026period,
title = {{Period Piece: NEXPTIME-complete problems on digraphs via Boolean network dynamics}},
author = {Florian Bridoux and Maximilien Gadouleau and David C. Kutner and Adrien Richard},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16561},
eprint = {2610.16561},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16561},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Period Piece: NEXPTIME-complete problems on digraphs via Boolean network dynamics
AU - Florian Bridoux
AU - Maximilien Gadouleau
AU - David C. Kutner
AU - Adrien Richard
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16561
UR - https://arxiv.org/abs/2610.16561
AB - The central object in this work is the Boolean network, a function f:{0,1}^V → {0,1}^V. Often identified with f is its dynamics D_f, the digraph with exactly {x → 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 ⊨ ϕ. 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→ 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 ∃!x:x→ 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 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 ≥ 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 NP^NP, the second level of the polynomial hierarchy, though it remains NP^NP-complete.
ER -