Complexity of fixed point counting problems in Boolean networks

DOI10.1016/J.JCSS.2022.01.004MaRDI QIDQ2119407zbMATH OpenOpenAlexFDO

Authors Florian Bridoux, Amélia Durbec, Kévin Perrot, Adrien Richard

Publication date 29 March 2022

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.02513

zbMATH Keywords

Boolean networkscomplexityfixed pointsinteraction graph

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A Boolean network (BN) with $n$ components is a discrete dynamical system described by the successive iterations of a function $f:{0,1}^{n}o{0,1}^n$. This model finds applications in biology, where fixed points play a central role. For example, in genetic regulations, they correspond to cell phenotypes. In this context, experiments reveal the existence of positive or negative influences among components: component $i$ has a positive (resp. negative) influence on component $j$ meaning that $j$ tends to mimic (resp. negate) $i$. The digraph of influences is called signed interaction digraph (SID), and one SID may correspond to a large number of BNs (which is, in average, doubly exponential according to $n$). The present work opens a new perspective on the well-established study of fixed points in BNs. When biologists discover the SID of a BN they do not know, they may ask: given that SID, can it correspond to a BN having at least/at most $k$ fixed points? Depending on the input, we prove that these problems are in $extrmP$ or complete for $extrmNP$, $extrm{NP}^{extrmNP}$, $$ or $extrmNEXPTIME$. In particular, we prove that it is $extrmNP$-complete (resp. $extrmNEXPTIME$-complete) to decide if a given SID can correspond to a BN having at least two fixed points (resp. no fixed point).

Recommendations

• Complexity of maximum fixed point problem in Boolean networks
• On the computation of fixed points in Boolean networks
• Complexity of limit-cycle problems in Boolean networks
• scientific article; zbMATH DE number 42045
• Unconventional Computation
• On the Complexity of Negation-Limited Boolean Networks
• Fixed points of Boolean networks, guessing graphs, and coding theory
• On the complexity of finding the number of solutions of systems of Boolean equations
• Number of fixed points and disjoint cycles in monotone Boolean networks
• Complexity Dichotomies for Counting Problems

Cites work

• A lattice-theoretical fixpoint theorem and its applications
• A new fixed point approach for stable networks and stable marriages
• A new necessary condition on interaction graphs for multistationarity
• An extension of a combinatorial fixed point theorem of Shih and Dong
• Asynchronous simulation of Boolean networks by monotone Boolean networks
• Asynchronous threshold networks
• Boolean modeling of genetic regulatory networks
• Combinatorics of Boolean automata circuits dynamics
• Complexity of limit-cycle problems in Boolean networks
• Complexity of maximum fixed point problem in Boolean networks
• Cooperative Boolean systems with generically long attractors I
• Cooperative Boolean systems with generically long attractors. II
• Depth-First Search and Linear Graph Algorithms
• Dichotomy results for fixed-point existence problems for Boolean dynamical systems
• Fixed points and connections between positive and negative cycles in Boolean networks
• Fixed points and maximal independent sets in AND-OR networks
• Fixed points of Boolean networks, guessing graphs, and coding theory
• Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications
• Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework
• scientific article; zbMATH DE number 4042465 (Why is no real title available?)
• scientific article; zbMATH DE number 45557 (Why is no real title available?)
• scientific article; zbMATH DE number 50840 (Why is no real title available?)
• scientific article; zbMATH DE number 1216123 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Linear network coding
• Maximum number of fixed points in AND-OR-NOT networks
• Maximum number of fixed points in regulatory Boolean networks
• Multistationarity, the basis of cell differentiation and memory. II: Logical analysis of regulatory networks in terms of feedback circuits
• Number of fixed points and disjoint cycles in monotone Boolean networks
• On the complexity of feedback set problems in signed digraphs
• Permanents, Pfaffian orientations, and even directed circuits
• Pólya's permanent problem
• Positive and negative cycles in Boolean networks
• Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability
• Topological fixed points in Boolean networks

Cited in

(13)

• Computing maximal and minimal trap spaces of Boolean networks
• Complexity of local, global and universality properties in finite dynamical systems
• Complexity of maximum fixed point problem in Boolean networks
• Dichotomy results for fixed point counting in Boolean dynamical systems
• Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
• Maximum number of fixed points in AND-OR-NOT networks
• Fixed points of Boolean networks, guessing graphs, and coding theory
• Synchronizing Boolean networks asynchronously
• Counting fixed points and pure 2-cycles of tree cellular automata
• Period-3 orbits of sequential dynamical systems and their relationship to error-correcting codes over finite fields
• FO logic on cellular automata orbits equals MSO logic
• Dynamical stability of threshold networks over undirected signed graphs
• Complexity of limit-cycle problems in Boolean networks

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Complexity of fixed point counting problems in Boolean networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2119407)