PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Florian Bridoux, Maximilien Gadouleau, David C. Kutner, Adrien Richard

arXiv:2610.16561v1cs.DMcs.CCmath.CO

TL;DR

The paper asks how much can be decided about Boolean-network dynamics from an interaction digraph, particularly when the graph is known but the dynamics is not. It defines and analyzes dynamic-property existence for unsigned digraphs, proving NEXPTIME-completeness for a family of periodic-point properties and NPNP-completeness under bounded in-degree.

  • Problem

    Although interaction graphs may be known while Boolean-network dynamics remain unknown, the complexity of deciding whether an unsigned digraph admits a network with a specified dynamical property had not been explored.

    Source: §1.1 · p. 3, §1.2 · p. 5

  • Method

    The paper defines ϕ-Dynamic existence problems and establishes hardness through reductions from Unique Fixed Point, using odd-system constructions.

    Source: §1.2 · p. 5, §7 · p. 14

  • Results

    Period Piece(Λ, Σ) is NEXPTIME-complete, while its bounded-in-degree version is NPNP-complete for all d ≥ 2.

    Source: §1.2 · p. 5

  • Takeaways & Limitations

    Period Piece supplies a family of natural NEXPTIME-complete languages whose inputs are explicitly represented digraphs.

    Source: §1.2 · p. 6

    The complexity lower bound requires Λ and Σ to be non-empty and finite.

    Source: §10 · p. 17

Abstract

from arXiv · show

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. $\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 $\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{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 $\phi$-DYNAMIC collapses down to $\mathrm{NP}^{\mathrm{NP}}$, the second level of the polynomial hierarchy, though it remains $\mathrm{NP}^{\mathrm{NP}}$-complete.

1 Introduction

Boolean-network research asks how interaction-graph structure relates to dynamics, especially when the graph is known but the dynamics is unknown. This paper studies the converse existence question for unsigned digraphs and proves hardness for unique-fixed-point and periodic-point properties.

1.1 Background

  • Interaction graphs encode which components essentially depend on which others, while the underlying dynamics can remain unknown even when the graph is known.A fixed point is a stable state, and Robert’s theorem says an acyclic interaction graph forces convergence to a unique fixed point.Source: §1.1 · p. 3
  • Prior work on signed digraphs studied dynamical-property existence, while many related unsigned-digraph problems about fixed-point counts are polynomial-time solvable.The introduction contrasts those problems with the new hardness results for unsigned interaction graphs.Source: §1.1 · pp. 3–4, §1.2 · p. 4

1.2 Contributions

  • The paper introduces ϕ-Dynamic for unsigned digraphs: whether a graph is the interaction graph of a Boolean network satisfying a specified dynamical property.The decision problem is posed both for arbitrary input digraphs and for digraphs with bounded in-degree.Source: §1.2 · p. 4
  • Unique Fixed Point is NEXPTIME-complete, whereas its bounded-in-degree version is NPNP-complete for every d ≥ 2.The paper notes that this hardness is specific to Boolean networks: for any q ≠ 2, every digraph admits a q-state network with a unique fixed point.Source: §1.2 · p. 5
  • Period Piece(Λ, Σ) captures specified permutations of periodic points, including properties such as exactly k fixed points and a unique cycle of a specified length.For every finite non-empty Λ and Σ, Period Piece is NEXPTIME-complete and its bounded-in-degree version is NPNP-complete for all d ≥ 2.Source: §1.2 · p. 5
  • The Period Piece hardness proofs reduce from (d-)UFP, and the resulting family is presented as a natural NEXPTIME-complete language on explicitly represented digraphs.The paper contrasts these inputs with typical NEXPTIME-complete problems using succinct representations or binary integers.Source: §1.2 · pp. 5–6

2 Preliminaries

The preliminaries define Boolean-network dynamics, interaction graphs, and dynamical properties, then introduce the UFP problem. For strongly connected digraphs, UFP-dynamicity holds exactly when the graph is not a cycle.

2.1 Definitions and notations

  • A Boolean network maps configurations to configurations; its dynamics has configurations as vertices and an arc x → y exactly when f(x) = y.A fixed point is a configuration x with f(x) = x.Source: §2.1 · pp. 6–7
  • The interaction graph has an arc i → j when the local function at j depends essentially on state x_i, and F(G) denotes networks with interaction graph G.A dynamical property depends only on the isomorphism class of the network's dynamics.Source: §2.1 · p. 7
  • A dynamical property is FOΣi or FOΠi when its first-order quantifiers follow the corresponding bounded-alternation pattern.These fragments are closed under conjunction and disjunction.Source: §2.1 · p. 7

2.2 Basic results

  • A digraph is ϕ-dynamic when some network in F(G) has dynamics satisfying ϕ; UFP requires exactly one fixed point.UFP is expressed in FOΣ2.Source: §2.2 · p. 7
  • A strongly connected digraph is UFP-dynamic if and only if it is not a cycle.The proof sketch uses that every strongly connected digraph can be built from a cycle by successive ear additions, recursively constructing a network with a unique fixed point.Source: §2.2 · p. 7
  • For every digraph G, F0(G) is nonempty; if G is UFP-dynamic, then it has a network whose unique fixed point is 0.F0(G) consists of networks fixing 0, and UFP0(G) consists of networks with 0 as their unique fixed point.Source: §2.2 · p. 7

3 Complexity upper bounds

The section bounds the complexity of dynamic-property problems using logic-based arguments. General ϕ-Dynamic is in NEXPTIME for MSO2 properties, while bounded-in-degree cases admit polynomial-hierarchy upper bounds for FOΣi properties.

3 Complexity upper bounds

  • The NEXPTIME upper bound applies to MSO2 properties, which can quantify over vertex and edge sets and are more expressive than FO(=, →).The bounded-in-degree upper-bound argument is stated for first-order properties.Source: §3 · pp. 7–8
  • For properties ϕ in FOΣi, d-ϕ-Dynamic is in ΣP_i when the input digraph has in-degree at most d.A bounded-in-degree network is represented by local lookup tables, allowing evaluation at a configuration in O(n · d) time; the proof encodes the property’s quantified assignments in a polynomial-time machine.Source: §3 · p. 8
  • For any property ϕ expressible in MSO2, ϕ-Dynamic is in NEXPTIME.The proof encodes a candidate network and uses bounded treewidth of its dynamics to apply Courcelle’s theorem.Source: §3 · p. 8

4 Cycle functionality

The section studies the dynamics of chordless cycles under fixed external contexts, extending an acyclic-network convergence result. Depending on the context, the cycle contributes a unique fixed extension, multiple fixed extensions, or periodic behavior.

4 Cycle functionality

  • If an acyclic induced subgraph has all its in-neighbors inside the fixed context or the subgraph, that context extends uniquely to a fixed configuration and converges to it.This is a local version of Robert’s theorem, which says an acyclic interaction graph converges to one fixed point.Source: §4 · p. 8
  • A context fixes the external in-neighbors of a chordless cycle, and a functionality context gives each cycle component a copy-or-negate rule whose α signature determines its parity.An acyclic context instead fixes at least one cycle vertex to a constant.Source: §4 · p. 9
  • An acyclic context yields a unique fixed extension, while a positive context yields two distinct fixed extensions.These behaviors hold for a fixed context of the cycle.Source: §4 · p. 9
  • A negative context makes the cycle converge to a periodic configuration whose period is q · d, where d divides 2ℓ but not ℓ.The section applies the lemma only where no two cycles in the graph intersect at a vertex.Source: §4 · p. 9

5 Loop-to-cycle digraphs

The section focuses on loop-to-cycle digraphs, where global contexts determine fixed-point and periodic behavior. It gives a necessary-and-sufficient characterization of a unique fixed point and notes that satisfying its conditions depends delicately on paths from loops to terminal cycles.

5 Loop-to-cycle digraphs

  • A loop-to-cycle digraph has terminal components that are trivial or cycles of length at least two, initial components that are trivial or loops, and only trivial components in between.A single-vertex strong component is trivial if it has no edge and a loop if it has one.Source: §5 · p. 10
  • For a network over a loop-to-cycle digraph, every periodic configuration induces a fixed global context, with one such context for each assignment to the loop vertices.The context is fixed on all vertices outside the terminal cycles.Source: §5 · p. 10
  • An acyclic context for every terminal cycle gives a fixed point, while a positive context for at least one cycle and no negative contexts gives at least two fixed points.A negative context for a terminal cycle of length ℓ yields periodic behavior with period q · d, where d divides 2ℓ but not ℓ, and no fixed point extending that context.Source: §5 · p. 10
  • A network has a unique fixed point exactly when that point’s global context is acyclic for every terminal cycle and every other global context is negative for at least one.Whether these conditions hold depends delicately on the paths from loops to terminal cycles.Source: §5 · p. 11

6 Odd-systems

Odd-systems encode Boolean constraints through parity conditions, and circuit fixed points can be represented exactly as their nonzero solutions. This encoding also carries formula satisfying assignments into odd-system solutions.

6 Odd-systems

  • An odd-system pairs variables with odd-constraints, each satisfied when its first subset is zero or its second subset has odd parity.The all-zero configuration is always a solution; Sol+(S) excludes it.Source: §6 · p. 11

6.1 Encoding circuits with odd-systems

  • A circuit has identity inputs, NOT gates with one in-neighbor, and AND gates with two; requiring a NOT gate ensures it does not fix 0.Its acyclic non-input portion gives exactly one fixed point extending each input configuration, so it has 2^|L| fixed points.Source: §6.1 · p. 11
  • The tight odd-system encoding assigns diff-constraints to NOT gates and two odd-constraints to each AND gate, and its nonzero solutions on circuit variables equal the circuit's fixed points.The encoding can be obtained in linear time.Source: §6.1 · p. 12

6.2 Encoding Boolean formulae with odd-systems

  • For a formula encoded by a circuit, satisfying assignments are precisely its nonzero encoded solutions whose output variable is 1.The formula's satisfying assignments can therefore be read from the circuit's fixed points or from the encoding's nonzero solutions.Source: §6.2 · p. 12

7 Odd-system vs digraph problem

Odd-System-vs-Digraph asks whether a Boolean network on a given digraph can avoid nonzero fixed points that satisfy an odd-system. Constraint gadgets implement odd-constraints, enabling reductions from tautology and onward to UFP hardness.

7 Odd-system vs digraph problem

  • Odd-System-vs-Digraph asks whether some h in F0(H) has no nonzero fixed point that is also a solution of S.The reduction framework uses this problem as the central ingredient in proving UFP hardness.Source: §7 · p. 13
  • Tautology reduces to Odd-System-vs-Digraph, proving the latter coNP-hard.A formula is a tautology exactly when every nonzero solution of its encoding has output 1, which makes the network's nonzero fixed points disjoint from those solutions.Source: §7 · p. 13
  • The (n, m)-gadget combines a path of length n and a cycle of length m + 1, with a loop on the path's first vertex and an arc from its end to the cycle.Its n path vertices and m cycle vertices are linear; the S-extension preserves loop-to-cycle structure and has maximum in-degree at most max(2, ∆−(H)).Source: §7 · pp. 13–14
  • An (A, B)-extension adds the constraint “xA = 0 or xB is odd” to the fixed-point set of a minimal extension of the network on H.Applying the construction successively for every odd-constraint produces the S-extension in polynomial time.Source: §7 · pp. 13–14

8 Complexity lower bound for d-UFP

The section reduces QSAT2 to UFP using a polynomial-time construction. The reduction yields NPNP-completeness even when the input digraph is loop-to-cycle and has maximum in-degree 2.

8 Complexity lower bound for d-UFP

  • NPNP-completeness holds for d-UFP for every d ≥ 2, and the hardness reduction already applies to loop-to-cycle digraphs.Theorem 13 constructs the corresponding loop-to-cycle graph with maximum in-degree 2.Source: §8 · pp. 14–15
  • The reduction starts from QSAT2 and constructs a graph using an odd-system and its S-extension of a digraph H.The odd-system includes the tight encoding of the formula's circuit; the construction establishes equivalence between positive QSAT2 instances and UFP-dynamic graphs.Source: §8 · p. 15

9 Complexity lower bound for UFP

A polynomial-time reduction from succinct 4-SAT establishes NEXPTIME-hardness of UFP. The result holds even for loop-to-cycle digraphs.

9 Complexity lower bound for UFP

  • The construction encodes the succinct formula with a circuit whose inputs represent clauses and positions and whose outputs identify a variable and literal sign.The graph construction uses the circuit's tight odd-system encoding and additional vertices and constraints.Source: §9 · pp. 15–16
  • UFP is NEXPTIME-complete, and the reduction proves NEXPTIME-hardness even for loop-to-cycle-UFP.Theorem 14 constructs the graph in polynomial time from a succinct representation of a 4-CNF formula.Source: §9 · p. 16
  • The formula is satisfiable if and only if its constructed graph is UFP-dynamic.Source: §9 · p. 16

10 Complexity lower bounds for Period Piece and d-Period Piece

Period Piece specifies the allowed short-cycle permutation pattern of a Boolean network, and its dynamic decision problem is complete for NEXPTIME; with bounded in-degree, the corresponding problem is complete for NP^NP. The hardness proof reduces from UFP, extending its complexity results to every finite non-empty choice of allowed lengths and permutations.

10 Complexity lower bounds for Period Piece and d-Period Piece

  • Period Piece(Λ, Σ) requires the periodic points on cycles of lengths in Λ to form a permutation in Σ.For Λ = {1} and Σ = {id1, …, idk}, this expresses between 1 and k fixed points; a singleton cycle permutation expresses a unique cycle of its specified length.Source: §10 · pp. 16–17
  • The lower-bound theorem assumes both Λ and Σ are finite and non-empty; empty Σ gives a vacuous property, while allowing all identity permutations expresses at least one fixed point.In the latter case, every digraph is a yes-instance.Source: §10 · p. 17
  • The reduction starts from UFP: it transforms a loop-to-cycle digraph into one encoding the chosen periodic-point property while keeping maximum in-degree at most 2.The construction subdivides terminal-cycle arcs and adds components to enforce the desired permutation pattern.Source: §10 · p. 17

A Proofs for Section 1 (Introduction)

B Proofs for Section 2 (Preliminaries)

For strongly connected digraphs, UFP-dynamicity holds exactly when the digraph is not a cycle. The proof constructs a Boolean network with a unique fixed point for each such digraph and normalizes fixed-point questions so the all-zero configuration is fixed.

B Proofs for Section 2 (Preliminaries)

  • A strongly connected digraph is UFP-dynamic if and only if it is not a cycle.On a cycle, every network with that interaction graph has either zero or two fixed points.Source: B Proofs for Section 2 (Preliminaries) · p. 20
  • Every strongly connected digraph that is not a cycle can be built by adding an ear to a strongly connected subgraph, enabling the proof's unique-fixed-point construction.The construction sets the new ear endpoint's function using its new in-neighbor and its other in-neighbors.Source: B Proofs for Section 2 (Preliminaries) · p. 20
  • Any interaction graph admits a network fixing 0, and if it admits a network with a unique fixed point, it also admits one whose unique fixed point is 0.The proof translates the network's input by its fixed point and translates its output back.Source: B Proofs for Section 2 (Preliminaries) · p. 20

C Proofs for Section 3 (Complexity upper bounds)

The proofs establish upper bounds for dynamical-property problems and develop cycle and odd-system tools used in the lower-bound reductions. In particular, they relate unique-fixed-point dynamicity to a constraint-system problem.

C Proofs for Section 3 (Complexity upper bounds)

  • For any MSO2 property, the dynamic decision problem is in NEXPTIME.The proof guesses a Boolean network, verifies its interaction graph, then model-checks its dynamics, whose functional digraph has treewidth at most 2.Source: C Proofs for Section 3 (Complexity… · pp. 20–21

D Proofs for Section 4 (Cycle functionality)

  • On a chordless cycle, an acyclic context extends uniquely to a fixed point, a positive context yields two fixed points, and a negative context leads to a periodic configuration with period q·d where d divides 2ℓ but not ℓ.The unique extension in the acyclic case is reached by convergence from the context.Source: D Proofs for Section 4 (Cycle… · pp. 22–23

E Proofs for Section 5 (Loop-to-cycle digraphs)

  • For loop-to-cycle digraphs, acyclic contexts on every terminal cycle yield a fixed point, while a positive context on at least one such cycle yields at least two fixed points.A negative context on a terminal cycle of length ℓ instead converges to a periodic configuration with period q·d, where d divides 2ℓ but not ℓ.Source: E Proofs for Section 5 (Loop-to-cycle… · p. 23

F Proofs for Section 6 (Odd-systems)

G Proofs for Section 7 (Odd-system vs digraph problem)

  • The S-extension construction links UFP-dynamicity of the extended graph to whether an odd-system and digraph instance has a witness.The proof states that G is UFP-dynamic exactly when there is an h in F0(H) with Fix+(h) ∩ Sol+(S) empty.Source: G Proofs for Section 7 (Odd-system vs… · p. 26

H Proofs for Section 8 (Complexity lower bound for d-UFP)

The proof reduces QSAT2 to UFP using a loop-to-cycle digraph of maximum in-degree 2. The construction encodes the formula with a circuit and odd-system constraints, and the resulting graph is UFP-dynamic exactly for yes-instances.

H Proofs for Section 8 (Complexity lower bound for d-UFP)

  • The constraints S combine the circuit encoding with additional constraints, so solutions of S capture the formula's encoded behavior.The construction's graph illustration notes that some vertices matter to the proof only through the constraints of Sψ.Source: Figure 6 · p. 26, H Proofs for Section 8 (Complexity… · p. 27
  • Gψ,E is a loop-to-cycle digraph with maximum in-degree 2, built as an S-extension of H.H includes the variables of the circuit encoding ψ and an additional vertex v.Source: H Proofs for Section 8 (Complexity… · p. 27
  • The construction makes Gψ,E UFP-dynamic when ψ, E is a yes-instance of QSAT2, and the converse also holds.The forward direction uses a satisfying partial assignment to define h; the reverse direction derives a QSAT2 witness from UFP-dynamicity.Source: H Proofs for Section 8 (Complexity… · p. 27

I Proofs for Section 9 (Complexity lower bound for UFP)

Theorem 14 reduces the UFP-dynamic question to a construction from a succinctly represented 4-CNF formula. Its proof encodes the formula in an odd-system and uses fixed points of a network on the constructed graph to relate the construction to satisfying assignments.

Theorem 14

  • Theorem 14 constructs a loop-to-cycle digraph from a succinctly represented 4-CNF formula for the UFP-dynamic reduction.The supplied theorem statement does not include the full equivalence in its conclusion.Source: I Proofs for Section 9 (Complexity… · p. 28

Construction

  • The graph H uses variables of the tight odd-system encoding of the circuit for ψ, together with s0, s1, and ν.The construction adds arcs from C to p0 and p1, from V to ν, and from s1 to p0, p1, and ν.Source: I Proofs for Section 9 (Complexity… · p. 28
  • The odd-system S combines the constraints encoding ψ with diff-constraints between s0 and s1 and between ρ and ν.The graph Gψ is the S-extension of H and remains a loop-to-cycle digraph.Source: I Proofs for Section 9 (Complexity… · p. 28

Encoding

  • A nonzero solution of S restricts to a fixed point of the circuit encoding ψ, and each such fixed point has exactly two extensions to solutions of S.The proof uses the tight encoding and the additional constraints to establish this correspondence.Source: I Proofs for Section 9 (Complexity… · p. 28

Forward direction

  • If ψ has a satisfying assignment, choices α and β make a selected literal true for every clause, defining a network h on H.The proof then analyzes fixed points of h to establish the reduction's forward direction.Source: I Proofs for Section 9 (Complexity… · p. 29

Reverse direction

  • The reverse direction extracts an assignment z from fixed points of h, with each clause c yielding a literal true under z.The argument uses the absence of an intersection between Fix+(h) and Sol+(S).Source: I Proofs for Section 9 (Complexity… · p. 29

Conclusion

J Proofs for Section 10 (Complexity lower bounds for Period Piece and d-Period Piece)

The proofs establish complexity lower bounds for Period Piece and bounded-in-degree variants, using constructions that encode prescribed periodic behavior in interaction graphs. They also develop lemmas on cycle periods and graph subdivisions used in the reductions.

Theorem 16

Theorem 17

  • Theorem 17 constructs in polynomial time a digraph GΛ,Σ of maximum in-degree at most 2 from a loop-to-cycle digraph G with a terminal cycle and maximum in-degree 2.The theorem statement's concluding equivalence is not included in the supplied passage.Source: J Proofs for Section 10 (Complexity… · p. 30

Lemma 30

  • For any permutation σ of degree k, a graph of maximum in-degree 2 supports a Boolean network whose periodic part is σ.The construction uses cyclic shifts whose unit configurations realize the cycles of σ; non-unit configurations are sent to a unit configuration.Source: J Proofs for Section 10 (Complexity… · pp. 30–31

Lemma 31

  • A digraph is UFP-dynamic exactly when all its subdivisions are UFP-dynamic.The proof reduces this to preserving the existence of a network with a unique fixed point when subdividing one arc.Source: J Proofs for Section 10 (Complexity… · p. 31

Lemma 32

  • If cycles in G are vertex-disjoint and have lengths that are powers of 2, every limit cycle of every network in F(G) has length a power of 2.The proof studies the network iterated twice and uses induction on the maximum cycle length and the number of vertices with non-loop out-neighbors.Source: J Proofs for Section 10 (Complexity… · pp. 32–33

Lemma 35

  • With a unique fixed point and terminal cycles of length 2^ℓ, every other periodic configuration has period at least 2^ℓ+1.This bound is used to separate the periods introduced by the constructed component from those of the other components.Source: J Proofs for Section 10 (Complexity… · pp. 33, 35

Lemmas 36–37

  • For a product of transformations, the number of limit cycles of length ℓ is constrained by the factor cycle lengths and their least common multiples.Under Lemma 37's unique-fixed-point and period-exclusion assumptions, combining f with h having an ℓ-cycle yields exactly one ℓ-cycle.Source: J Proofs for Section 10 (Complexity… · pp. 33–34

Theorem 17 proof

  • Theorem 17's construction uses subdivided copies of G alongside Hσ, whose periodic part realizes σ.The proof chooses the subdivision length and number of copies using bounds on Λ, Σ, and the longest terminal cycle.Source: J Proofs for Section 10 (Complexity… · pp. 30, 34
Loading 2610.16561v1…