TY - GEN

T1 - On the Impact of Treewidth in the Computational Complexity of Freezing Dynamics

AU - Goles, Eric

AU - Montealegre, Pedro

AU - Ríos Wilson, Martín

AU - Theyssier, Guillaume

N1 - Funding Information:
Keywords: Freezing automata networks · Treewidth · Fast parallel algorithm · Prediction · Nilpotency · Asynchronous reachability · Predecessor problem This reasearch was partially supported by French ANR project FANs ANR-18-CE40-0002 (G.T., M.R.W.) and ECOS project C19E02 (G.T., M.R.W.), ANID via PAI + Convocatoria Nacional Subvención a la Incorporación en la Academia Año 2017 + PAI77170068 (P.M.), FONDECYT 11190482 (P.M.), FONDECYT 1200006 (E.G., P.M.), STIC-AmSud CoDANet project 88881.197456/2018-01 (E.G., P.M.), ANID via PFCHA/DOCTORADO NACIONAL/2018 – 21180910 + PIA AFB 170001 (M.R.W).
Funding Information:
This reasearch was partially supported by French ANR project FANs ANR-18-CE400002 (G.T., M.R.W.) and ECOS project C19E02 (G.T., M.R.W.), ANID via PAI + Convocatoria Nacional Subvenci?n a la Incorporaci?n en la Academia A?o 2017 + PAI77170068 (P.M.), FONDECYT 11190482 (P.M.), FONDECYT 1200006 (E.G., P.M.), STIC-AmSud CoDANet project 88881.197456/2018-01 (E.G., P.M.), ANID via PFCHA/DOCTORADO NACIONAL/2018 ? 21180910 + PIA AFB 170001 (M.R.W).
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - An automata network is a network of entities, each holding a state from a finite set and evolving according to a local update rule which depends only on its neighbors in the network’s graph. It is freezing if there is an order on states such that the state evolution of any node is non-decreasing in any orbit. They are commonly used to model epidemic propagation, diffusion phenomena like bootstrap percolation or cristal growth. 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 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 problem when the three parameters are bounded, hence showing that the problem is in NC. 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 graphs with sufficiently large treewidth.

AB - An automata network is a network of entities, each holding a state from a finite set and evolving according to a local update rule which depends only on its neighbors in the network’s graph. It is freezing if there is an order on states such that the state evolution of any node is non-decreasing in any orbit. They are commonly used to model epidemic propagation, diffusion phenomena like bootstrap percolation or cristal growth. 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 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 problem when the three parameters are bounded, hence showing that the problem is in NC. 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 graphs with sufficiently large treewidth.

KW - Asynchronous reachability

KW - Fast parallel algorithm

KW - Freezing automata networks

KW - Nilpotency

KW - Predecessor problem

KW - Prediction

KW - Treewidth

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

U2 - 10.1007/978-3-030-80049-9_24

DO - 10.1007/978-3-030-80049-9_24

M3 - Conference contribution

AN - SCOPUS:85112209224

SN - 9783030800482

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 260

EP - 272

BT - Connecting with Computability - 17th Conference on Computability in Europe, CiE 2021, Proceedings

A2 - De Mol, Liesbeth

A2 - Weiermann, Andreas

A2 - Manea, Florin

A2 - Fernández-Duque, David

PB - Springer Science and Business Media Deutschland GmbH

T2 - 17th Conference on Computability in Europe, CiE 2021

Y2 - 5 July 2021 through 9 July 2021

ER -