Complexity of limit-cycle problems in Boolean networks

DOI10.1007/978-3-030-67731-2_10zbMATH Open1490.68117arXiv2001.07391OpenAlexW3126498632MaRDI QIDQ831798FDOQ831798

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

Publication date: 24 March 2022

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Blocs-H-matrices et convergence des méthodes itératives classiques par blocs
• Combinatorics of Boolean automata circuits dynamics
• A logical calculus of the ideas immanent in nervous activity
• Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework
• Fixed points and maximal independent sets in AND-OR networks
• On the number of different dynamics in Boolean networks with deterministic update schedules
• Necessary conditions for multistationarity in discrete dynamical systems
• Negative circuits and sustained oscillations in asynchronous automata networks
• Limit cycles and update digraphs in Boolean networks
• Itérations sur des ensembles finis et automates cellulaires contractants
• Complexity of maximum fixed point problem in Boolean networks
• Neural networks and complexity theory
• Number of Fixed Points and Disjoint Cycles in Monotone Boolean Networks

Cited In (5)

• Computing maximal and minimal trap spaces of Boolean networks
• Existence and non existence of limit cycles in Boolean networks
• Complexity of fixed point counting problems in Boolean networks
• Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
• Complexity of limit cycles with block-sequential update schedules in conjunctive networks

Recommendations

• Limit cycles and update digraphs in Boolean networks 👍 👎
• On the complexity of negation-limited Boolean networks (preliminary version) 👍 👎
• On the Complexity of Negation-Limited Boolean Networks 👍 👎
• Existence and non existence of limit cycles in Boolean networks 👍 👎
• Complexity of fixed point counting problems in Boolean networks 👍 👎
• Complexity of maximum fixed point problem in Boolean networks 👍 👎
• On the computation of fixed points in Boolean networks 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)