{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.16561",
  "author_total": 4,
  "authors": [
    {
      "name": "Florian Bridoux"
    },
    {
      "name": "Maximilien Gadouleau"
    },
    {
      "name": "David C. Kutner"
    },
    {
      "name": "Adrien Richard"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/6zmh0qbc3mjc7.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.16561",
  "fulltext_url": null,
  "id": "6zmh0qbc3mjc7",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.16561",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.CC"
    ],
    [
      "arxiv",
      "cs.DM"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "1703|Advanced Graph Theory Research"
    ]
  ],
  "openalex": "W7221795562",
  "pdf_url": "https://arxiv.org/pdf/2610.16561",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-12",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/6zmh0qbc3mjc7.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:29:15Z",
      "native_id": "2610.16561",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.16561"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Period Piece: NEXPTIME-complete problems on digraphs via Boolean network dynamics",
  "title_text": "Period Piece: NEXPTIME-complete problems on digraphs via Boolean network dynamics",
  "type": "preprint",
  "updated_at": "2026-10-30T12:29:15Z",
  "url": "https://research.draconitic.com/paper/6zmh0qbc3mjc7",
  "venue": "arXiv",
  "versions": []
}