Complexity of limit-cycle problems in Boolean networks

DOI10.1007/978-3-030-67731-2_10MaRDI QIDQ831798zbMATH OpenOpenAlexFDO

Authors Florian Bridoux, Caroline Gaze-Maillot, Kévin Perrot, Sylvain Sené

Publication date 24 March 2022

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

Mathematics Subject Classification ID

Dynamical systems in biology (37N25) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Dynamical systems involving maps of trees and graphs (37E25)

Abstract: Boolean networks are a general model of interacting entities, with applications to biological phenomena such as gene regulation. Attractors play a central role, and the schedule of entities update is a priori unknown. This article presents results on the computational complexity of problems related to the existence of update schedules such that some limit-cycle lengths are possible or not. We first prove that given a Boolean network updated in parallel, knowing whether it has at least one limit-cycle of length $k$ is $extNP$-complete. Adding an existential quantification on the block-sequential update schedule does not change the complexity class of the problem, but the following alternation brings us one level above in the polynomial hierarchy: given a Boolean network, knowing whether there exists a block-sequential update schedule such that it has no limit-cycle of length $k$ is $Sigm{a}_2^{e}xtP$-complete.

Recommendations

• On the Complexity of Negation-Limited Boolean Networks
• Complexity of maximum fixed point problem in Boolean networks
• Complexity of fixed point counting problems in Boolean networks
• scientific article; zbMATH DE number 42045
• Existence and non existence of limit cycles in Boolean networks
• On the complexity of negation-limited Boolean networks (preliminary version)
• Limit cycles and update digraphs in Boolean networks
• On the computation of fixed points in Boolean networks
• scientific article; zbMATH DE number 769371

Cites work

• scientific article; zbMATH DE number 4201618 (Why is no real title available?)
• scientific article; zbMATH DE number 3771418 (Why is no real title available?)
• scientific article; zbMATH DE number 45557 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 3266639 (Why is no real title available?)
• A logical calculus of the ideas immanent in nervous activity
• Block-sequential update schedules and Boolean automata circuits
• Blocs-H-matrices et convergence des méthodes itératives classiques par blocs
• Combinatorics of Boolean automata circuits dynamics
• Complexity of maximum fixed point problem in Boolean networks
• Fixed points and maximal independent sets in AND-OR networks
• Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework
• Itérations sur des ensembles finis et automates cellulaires contractants
• Limit cycles and update digraphs in Boolean networks
• Necessary conditions for multistationarity in discrete dynamical systems
• Negative circuits and sustained oscillations in asynchronous automata networks
• Neural networks and complexity theory
• Number of fixed points and disjoint cycles in monotone Boolean networks
• On the number of different dynamics in Boolean networks with deterministic update schedules

Cited in

(9)

• Limit cycles and update digraphs in Boolean networks
• Complexity of limit cycles with block-sequential update schedules in conjunctive networks
• Parallel and sequential computation on Boolean networks
• Existence and non existence of limit cycles in Boolean networks
• Block-sequential update schedules and Boolean automata circuits
• Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
• Complexity of fixed point counting problems in Boolean networks
• Computing maximal and minimal trap spaces of Boolean networks
• On the number of different dynamics in Boolean networks with deterministic update schedules

This page was built for publication: Complexity of limit-cycle problems in Boolean networks

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