key: cord-0046143-yfmgrvyy
authors: Noûs, Camille; Perrot, Kévin; Sené, Sylvain; Venturini, Lucas
title: #P-completeness of Counting Update Digraphs, Cacti, and Series-Parallel Decomposition Method
date: 2020-06-24
journal: Beyond the Horizon of Computability
DOI: 10.1007/978-3-030-51466-2_30
sha: d70b0179652cd368a69bf54fb320fa9bb568c6bf
doc_id: 46143
cord_uid: yfmgrvyy

Automata networks are a very general model of interacting entities, with applications to biological phenomena such as gene regulation. In many contexts, the order in which entities update their state is unknown, and the dynamics may be very sensitive to changes in this schedule of updates. Since the works of Aracena et al., it is known that update digraphs are pertinent objects to study non-equivalent block-sequential update schedules. We prove that counting the number of equivalence classes, that is a tight upper bound on the synchronism sensitivity of a given network, is [Formula: see text]-complete. The problem is nevertheless computable in quasi-quadratic time for oriented cacti, and for oriented series-parallel graphs thanks to a decomposition method.

Since their introduction by McCulloch and Pitts in the 1940s through the well known formal neural networks [20] , automata networks (ANs) are a general model of interacting entities in finite state spaces. The field has important contributions to computer science, with Kleene's finite state automata [17] , linear shift registers [14] and linear networks [12] . At the end of the 1960s, Kauffman and Thomas (independently) developed the use of ANs for the modeling of biological phenomena such as gene regulation [16, 28] , providing a fruitful theoretical framework [26] .

ANs can be considered as a collection of local functions (one per component), and influences among components may be represented as a so called interaction digraph. In many applications the order of components update is a priori unknown, and different schedules may greatly impact the dynamical properties Mainly funded by our salaries as French State agents (affiliated to Laboratoire Cogitamus (CN), Aix-Marseille Univ., Univ. de Toulon, CNRS, LIS, Marseille, France (KP, SS and LV), Univ. Côte d'Azur, CNRS, I3S, Sophia Antipolis, France (KP), andÉcole normale supérieure de Lyon, Computer Science department, Lyon, France (LV)), and secondarily by the projects ANR-18-CE40-0002 FANs, ECOS-CONICYT C16E01, STIC AmSud 19-STIC-03 (Campus France 43478PD). of the system. It is known since the works of Aracena et al. in [4] that update digraphs (consisting of labeling the arcs of the interaction digraphs with ⊕ and ) capture the correct notion to consider a biologically meaningful family of update schedules called block-sequential in the literature. Since another work of Aracena et al. [3] a precise characterization of the valid labelings has been known, but their combinatorics remains puzzling. After formal definitions and known results in Sects. 2 and 3, we propose in Sect. 4 an explanation for this difficulty, through the lens of computational complexity theory: we prove that counting the number of update digraphs (valid {⊕, }-labelings) is #P-complete. In Sect. 5 we consider the problem restricted to the family of oriented cactus graphs and give a O(n 2 log n log log n) time algorithm, and finally in Sect. 6 we present a decomposition method leading to a O(n 2 log 2 n log log n) algorithm for oriented series-parallel graphs.

Given a finite alphabet [q] = {1, . . . , q}, an automata network (AN) of size n is a function f : [q] n → [q] n . We denote x i the component i ∈ [n] of some configuration x ∈ [q] n . ANs are more conveniently seen as n local functions

The interaction digraph captures the effective dependencies among components, and is defined as

It is well known that the schedule of components update may have a great impact on the dynamics [5, 13, 21, 23] . A block-sequential update schedule B = (B 1 , . . . , B t ) is an ordered partition of [n], defining the following dynamics

i.e., parts are updated sequentially one after the other, and components within a part are updated in parallel. For the parallel update schedule B par = ([n]), we have f (B par ) = f . Block-sequential update schedules are a classical family of update schedules considered in the literature, because they are perfectly fair: every local function is applied exactly once during each step. Equipped with an update schedule, f (B) is a discrete dynamical system on [q] n . In the following we will shortly say update schedule to mean block-sequential update schedule. It turns out quite intuitively that some update schedules will lead to the same dynamics, when the ordered partitions are very close and the difference relies on components far apart in the interaction digraph (see an example on Fig. 1 ). Aracena et al. introduced in [4] the notion of update digraph to capture this fact. To an update schedule one can associate its update digraph, which is a {⊕, }-labeling of the arcs of the interaction digraph of the AN, such that (i, j) is negative ( ) when i is updated strictly before j, and positive (⊕) otherwise. Formally, given an update schedule B = (B 1 , . . . , B t ),

Remark 1. Loops are always labeled ⊕, hence we consider our digraphs loopless.

The following result has been established: given two update schedules, if the relative order of updates among all adjacent components are identical, then the dynamics are identical. It leads naturally to an equivalence relation on update schedules, at the heart of the present work.

It is very important to note that, though every update schedule corresponds to a {⊕, }-labeling of G f , the reciprocal of this fact is not true. For example, a cycle with all arcs labeled would lead to a contradiction where components are updated strictly before themselves. Aracena et al. gave a precise characterization of valid update digraphs (i.e. the ones corresponding to at least one update schedule).

there is no cycle (i 0 , i 1 , . . . , i k ), with i 0 = i k , of length k > 0 such that both:

In words, the multidigraph where the orientation of negative arcs is reversed, does not contain a cycle with at least one negative arc (forbidden cycle).

As a corollary, one can decide in polynomial time whether a labeling is valid (Valid-UD Problem is in P). We are interested in the following.

Input: a digraph G = (V, A). Output: #UD(G) = |{lab : A → { , ⊕} | lab is valid}|.

The following definition is motivated by Theorem 2.

Remark 2. We can restrict our study to connected digraphs (that is, such thatḠ is connected), because according to Theorem 2 the only invalid labelings contain (forbidden) cycles. Given some G with V 1 , . . . , V k its connected components, and

, and this decomposition can be computed in linear time from folklore algorithms.

Proof. The following non-deterministic algorithm runs in polynomial time (Valid-UD Problem is in P), and its number of accepting branches equals #UD(G):

1. guess a labeling lab : A → {⊕, } (polynomial space), 2. accept if lab is valid, otherwise reject.

The consideration of update digraphs has been initiated by Aracena et al. in 2009 [4] , with their characterization (Theorem 2) in [3] . In Sect. 4 we will present a problem closely related to #UD that has been proven to be NP-complete in [3] , UD Problem, and bounds that we can deduce on #UD (Corollary 1, from [2] ). In [1] the authors present an algorithm to enumerate update digraphs, and prove its correctness. They also consider a surprisingly complex question: given an AN f , knowing whether there exist two block-sequential update schedules B, B such that f (B) = f (B ) , is NP-complete. The value of #UD(G) is known to be 3 n − 2 n+1 + 2 for bidirected cycles on n vertices [23] , and to equal n! if and only if the digraph is a tournament on n vertices [2] .

The authors of [3] have exhibited an insightful relation between valid labelings and feedback arc sets of a digraph. We recall that a feedback arc set (FAS) of

and its size is |F |. This relation is developed inside the proof of NP-completeness of the following decision problem. We reproduce it as a Lemma.

Input: a digraph G = (V, A) and an integer k. Question: does there exist a valid labeling of size at most k?

The size of a labeling is its number of ⊕ labels. It is clear that minimizing the number of ⊕ labels (or equivalently maximizing the number of labels) is the difficult direction, the contrary being easy because lab(a) = ⊕ for all a ∈ A is always valid (and corresponds to the parallel update schedule B par ). (2, 3) , (3, 1)} is a FAS, but the corresponding labeling is not valid: component 3 is updated prior to 2, 1 not prior to 2, and 3 not prior to 1, which is impossible.

Lemma 1 (appears in [3, Theorem 16] ). There exists a bijection between minimal valid labelings and minimal feedback arc sets of a digraph G = (V, A).

Proof (sketch). To get the bijection, we simply identify a labeling lab with its set of arcs labeled ⊕,

Any valid labeling corresponds to a FAS, and every minimal FAS corresponds to a valid labeling, hence the following bounds hold. The strict inequality for the lower bound comes from the fact that labeling all arcs ⊕ does not give a minimal FAS, as noted in [2] where the authors also consider the relation between update digraphs (valid labelings) and feedback arc sets, but from another perspective.

From Lemma 1 and results on the complexity of FAS counting problems presented in [22] , we have the following corollary (minimum FAS are minimal, hence the identity is a parsimonious reduction from the same problems on FAS).

However the correspondence given in Lemma 1 does not hold in general: there may exist some FAS F such that lab with F lab = F is not a valid labeling (see Fig. 2 for an example). As a consequence we do not directly get a counting reduction to #UD. It nevertheless holds that #UD is #P-hard, with the following reduction.

Proof. We present a (polynomial time) parsimonious reduction from the problem of counting the number of acyclic orientations of an undirected graph, proven to be #P-hard in [18] .

Given an undirected graph G = (V, E), let ≺ denote an arbitrary total order on V . Construct the digraph G = (V, A) with A the orientation of E according to ≺, i.e. (u, v) ∈ A ⇐⇒ {u, v} ∈ E and u ≺ v. An example is given on Fig. 3  (left) . A key property is that G is acyclic, because A is constructed from an order ≺ on V (a cycle would have at least one arc (u, v) with v ≺ u). We claim that there is a bijection between the valid labelings of G and the acyclic orientations of G: to a valid labeling lab : A → {⊕, } of G we associate the orientation

First remark that O is indeed an orientation of E: each edge of E is transformed into an arc of A, and each arc of A is transformed into an arc of O. An example is given on Fig. 3 (right) . Now observe that O is exactly obtained from G by reversing the orientation of arcs labeled by lab. Furthermore, a cycle in O must contain at least one arc labeled by lab, because G is acyclic and ⊕ labels copy the orientation of G . The claim therefore follows directly from the characterization of Theorem 2.

The difficulty of counting the number of update digraphs comes from the interplay between various possible cycles, as is assessed by the parsimonious reduction from acyclic orientations counting problem to #UD. Answering the problem for an oriented tree with m arcs is for example very simple: all of the 2 m labelings are valid. Cactus undirected graphs are defined in terms of very restricted entanglement of cycles, which we can exploit to compute the number of update digraphs for any orientation of its edges.

Cacti may intuitively be thought as trees with cycles. This is indeed the idea behind the skeleton of a cactus introduced in [9] , via the following notions:

-a c-vertex is a vertex of degree two included in exactly one cycle, -a g-vertex is a vertex not included in any cycle, -remaining vertices are h-vertices, and a graft is a maximal subtree of g-and h-vertices with no two h-vertices belonging to the same cycle. Then a cactus can be decomposed as grafts and cycles (two classes called blocks), connected at h-vertices according to a tree skeleton. These notions directly apply to oriented cacti (see an example on Fig. 4) . Proof. The result is obtained from the skeleton of an oriented cactus G, since potential forbidden cycles are limited to within blocks of the skeleton. From this independence, any union of valid labelings on blocks is valid, and we have the product

where G is the set of grafts of G, C is the set of cycles forming directed cycles, C is the set of cycles not forming directed cycles, and |H| is the number of arcs in block H. Indeed, grafts cannot create forbidden cycles hence any {⊕, }labeling will be valid, cycles forming a directed cycle can create exactly one forbidden cycle (with labels on all arcs), and cycles not forming a directed cycle can create exactly two forbidden cycles (one for each possible direction of the cycle). In a first step the skeleton of a cactus can be computed in linear time [9] . Then, since the size n of the input is equal (up to a constant) to the number of arcs, the size of the output contains O 

In this section we present a divide and conquer method in order to solve #UD, i.e. in order to count the number of valid labelings (update digraphs) of a given digraph. What will be essential in this decomposition method is not the orientation of arcs, but rather the topology of the underlying undirected (multi)graph G. The (de)composition is based on defining two endpoints on our digraphs, and composing them at their endpoints. It turns out to be closely related to series-parallel graphs first formalized to model electric networks in 1892 [19] . In Subsect. 6.1 we present the operations of composition, and in Subsect. 6.2 we show how it applies to the family of oriented series-parallel graphs.

Let us first introduce some notations and terminology on the characterization of valid labelings provided by Theorem 2. Given lab : A → {⊕, }, we denotẽ G lab = (V,Ã) the multidigraph obtained by reversing the orientation of negative arcs:

For simplicity we abuse the notation and still denote lab the labeling of the arcs ofG lab (arcs keep their label from G toG lab ). From Theorem 2, lab is a valid labeling if and only ifG lab does not contain any cycle with at least one arc labeled , called forbidden cycle (it may contain cycles with all arcs labeled ⊕). A path from i to j inG lab is called negative if it contains at least one arc labeled , and positive otherwise.

A source-sink labeled graph (ss-graph) (G, α, β) is a multigraph G with two distinguished vertices α = β. A triple (G, α, β) with G a digraph such that (Ḡ, α, β) is a ss-graph, is called an oriented ss-graph (oss-graph).

We can decompose the set of update digraphs (denoted UD(G) = {lab : A → {⊕, } | lab is valid}) into an oss-graph (G, α, β), based on the follow sets.

UD(G) + α→β = {lab ∈ UD(G) | there exists a path from α to β inG lab , and all paths from α to β inG lab are positive}

We define analogously UD(G) + β→α , UD(G) − β→α , UD(G) ∅ β→α , and partition UD(G) as:

Notice that the three missing combinations, UD(G) +,− α,β , UD(G) −,+ α,β and UD(G) −,− α,β , would always be empty because such labelings contain a forbidden cycle. For 

where #UD(G) s,t α,β = |UD(G) s,t α,β |. Oss-graphs may be thought as black boxes, we will compose them using the values of #UD(G) s,t α,β , regardless of their inner topologies.

We define three types of compositions (see Fig. 5 ).

-The series composition of two oss-graphs (G, α, β) and Remark that the three types of compositions from Definition 4 also apply to (undirected) ss-graph (Ḡ, α, β). Series and free compositions differ on the endpoints of the obtained oss-graph, which has important consequences on counting the number of update digraphs, as stated in the following results. We will see in Theorem 6 from Subsect. 6.2 that both series and free compositions are needed in order to decompose the family of (general) oriented series-parallel graphs (to be defined). Proof (sketch). The proof is analogous to Lemma 2, except that some couples may create invalid labelings.

Note that Remark 3 also applies to Lemmas 2 and 3. For the free composition the count is easier. Proof. The endpoints of the oss-graph (D, α, β) are the endpoints of the ossgraph (G, α, β), and it is not possible to create a forbidden cycle in the union of a valid labeling on G and a valid labeling of G , therefore the union is always a valid labeling of D, each one belonging to the part (s, t) of (D, α, β) corresponding to the part (s, t) ∈ S of (G, α, β).

The series and parallel compositions of Definition 4 correspond exactly to the class of two-terminal series-parallel graphs from [25, 29] .

A ss-graph (G, α, β) is two-terminal series-parallel (a ttsp-graph) if and only if one the following holds.

-(G, α, β) is a base ss-graph with two vertices α, β and one edge {α, β}.

-(G, α, β) is obtained by a series or parallel composition 1 of two ttsp-graphs.

In this case G alone is called a blind ttsp-graph.

Adding the free composition allows to go from two-terminal series-parallel graphs to (general) series-parallel graphs [11, 29] . More precisely, it allows exactly to add tree structures to ttsp-graphs, as we argue now (ttsp-graphs do not contain arbitrary trees, its only acyclic graphs being simple paths; e.g. one cannot build a claw from Definition 5).

A multigraph G is series-parallel (sp-graph) if and only if all its 2-connected components are blind ttsp-graphs. A digraph G such thatḠ is an sp-graph, is called an oriented sp-graph (osp-graph).

The family of sp-graphs corresponds to the multigraphs obtained by series, parallel and free compositions from base ss-graphs. (G, α, β) is obtained by series, parallel and free compositions from base ss-graphs, for some α, β.

Proof (sketch). Free compositions allow to build all sp-graphs, because it offers the possibility to create the missing tree structures of ttsp-graphs: arbitrary 1-connected components linking 2-connected ttsp-graphs. Moreover free compositions do not go beyond sp-graphs, since the obtained multigraphs still have treewidth 2.

Theorem 7. #UD is solvable in time O(n 2 log 2 n log log n) on osp-graphs (without promise).

Proof (sketch). This is a direct consequence of Lemmas 2, 3 and 4, because all values are in O(2 n ) (the number of {⊕, }-labelings) hence on O(n) bits, the values of #UD(G) s,t α,β are trivial for oriented base ss-graphs, and we perform O(n log n) compositions (to reach Formula 1). The absence of promise comes from a linear time recognition algorithm in [29] for ttsp-graphs, which also provides the decomposition structure.

Again, Remark 3 applies to Theorem 7.

Our main result is the #P-completeness of #UD, i.e. of counting the number of non-equivalent block-sequential update schedules of a given AN f . We proved that this count can nevertheless be done in O(n 2 log n log log n) time for oriented cacti, and in O(n 2 log 2 n log log n) time for oriented series-parallel graphs. This last result has been obtained via a decomposition method providing a divideand-conquer algorithm.

Remark that cliques or tournaments are intuitively difficult instances of #UD, because of the intertwined structure of potential forbidden cycles. It turns out that K 4 is the smallest clique that cannot be build with series, parallel and free decompositions, and that series-parallel graphs (Definition 6) correspond exactly to the family of K 4 -minor-free graphs [11] (it is indeed closed by minor [27] ). In further works we would like to extend this characterization and the decomposition method to (di)graphs with multiple endpoints.

The complexity analysis of the algorithms presented in Theorems 5 and 7 may be improved, and adapted to the parallel setting using the algorithms presented in [7, 15] . One may also ask for which other classes of digraphs is #UD(G) computable efficiently (in polynomial time)? Since we found such an algorithm for graphs of treewidth 2, could it be that the problem is fixed parameter tractable on bounded treewidth digraphs? Rephrased more directly, could a general tree decomposition (which, according to the proof of Theorem 6, is closely related to the series-parallel decomposition for treewidth 2) be exploited to compute the solution to #UD? Alternatively, what other types of decompositions one can consider in order to ease the computation of #UD(G)?

Finally, from the multiplication obtained for one-point join of two graphs (Lemma 4 on free composition), we may ask whether #UD(G) is an evaluation of the Tutte polynomial? From its universality [8] , it remains to know whether there is a deletion-contradiction reduction. However defining a Tutte polynomial for directed graphs is still an active area of research [6, 10, 24, 30] .

On the number of different dynamics in Boolean networks with deterministic update schedules

On the number of update digraphs and its relation with the feedback arc sets and tournaments

Combinatorics on update digraphs in Boolean networks

On the robustness of update schedules in Boolean networks

Limit cycles and update digraphs in Boolean networks

Tutte polynomials for directed graphs

Parallel algorithms for series parallel graphs

A decomposition for combinatorial geometries

A linear algorithm for the pos/neg-weighted 1-median problem on a cactus

Abelian sandpile model and Biggs-Merino polynomial for directed graphs

Topology of series-parallel networks

The theory of autonomous linear sequential networks

A guided tour of asynchronous cellular automata

Canonical forms for information-lossless finite-state logical machines

An Introduction to Parallel Algorithms

Metabolic stability and epigenesis in randomly constructed genetic nets

Representation of events in nerve nets and finite automata. Project RAND RM-704

Hard enumeration problems in geometry and combinatorics

The combinations of resistances

A logical calculus of the ideas immanent in nervous activity

Synchronism versus asynchronism in monotonic Boolean automata networks

On the complexity of counting feedback arc sets

Maximum sensitivity to update schedule of elementary cellular automata over periodic configurations

Chip-firing game and partial Tutte polynomial for Eulerian digraphs

The number of two-terminal series-parallel networks

Blocs-H-matrices et convergence des méthodes itératives classiques par blocs

Graph minors. XX. Wagner's conjecture

Boolean formalization of genetic control circuits

The recognition of series parallel digraphs

Tutte-Whitney polynomials for directed graphs and maps