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 -