TY - JOUR

T1 - On the parameterized complexity of freezing dynamics

AU - Goles, Eric

AU - Montealegre, Pedro

AU - Ríos-Wilson, Martín

AU - Theyssier, Guillaume

N1 - Publisher Copyright:
© 2024 Elsevier Inc.

PY - 2024/6

Y1 - 2024/6

N2 - In this paper we establish how alphabet size, treewidth and maximum degree of the underlying graph are key parameters which influence the overall computational complexity of finite freezing automata networks. First, we define a general decision problem, called Specification Checking Problem, that captures many classical decision problems such as prediction, nilpotency, predecessor, asynchronous reachability. Then, we present a fast-parallel algorithm that solves the general model checking problem when the three parameters are bounded, hence showing that the problem is in NC. Moreover, we show that the problem is in XP on the parameters tree-width and maximum degree. Finally, we show that these problems are hard from two different perspectives. First, the general problem is W[2]-hard when taking either treewidth or alphabet as single parameter and fixing the others. Second, the classical problems are hard in their respective classes when restricted to families of graph with sufficiently large treewidth.

AB - In this paper we establish how alphabet size, treewidth and maximum degree of the underlying graph are key parameters which influence the overall computational complexity of finite freezing automata networks. First, we define a general decision problem, called Specification Checking Problem, that captures many classical decision problems such as prediction, nilpotency, predecessor, asynchronous reachability. Then, we present a fast-parallel algorithm that solves the general model checking problem when the three parameters are bounded, hence showing that the problem is in NC. Moreover, we show that the problem is in XP on the parameters tree-width and maximum degree. Finally, we show that these problems are hard from two different perspectives. First, the general problem is W[2]-hard when taking either treewidth or alphabet as single parameter and fixing the others. Second, the classical problems are hard in their respective classes when restricted to families of graph with sufficiently large treewidth.

KW - Asynchronous reachability

KW - Fast parallel algorithms

KW - Freezing automata networks

KW - Nilpotency problem

KW - Predecessor problem

KW - Prediction problem

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85191327876&partnerID=8YFLogxK

U2 - 10.1016/j.aam.2024.102706

DO - 10.1016/j.aam.2024.102706

M3 - Article

AN - SCOPUS:85191327876

SN - 0196-8858

VL - 157

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

M1 - 102706

ER -