
AlvarezMiranda, E., & Pereira, J. (2019). On the complexity of assembly line balancing problems. Comput. Oper. Res., 108, 182–186.
Abstract: Assembly line balancing is a family of combinatorial optimization problems that has been widely studied in the literature due to its simplicity and industrial applicability. Most line balancing problems are NPhard as they subsume the bin packing problem as a special case. Nevertheless, it is common in the line balancing literature to cite [A. Gutjahr and G. Nemhauser, An algorithm for the line balancing problem, Management Science 11 (1964) 308315] in order to assess the computational complexity of the problem. Such an assessment is not correct since the work of Gutjahr and Nemhauser predates the concept of NPhardness. This work points at over 50 publications since 1995 with the aforesaid error. (C) 2019 Elsevier Ltd. All rights reserved.



Araujo, J., Ducoffe, G., Nisse, N., & Suchan, K. (2018). On interval number in cycle convexity. Discret. Math. Theor. Comput. Sci., 20(1), 35 pp.
Abstract: Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by in(cc)(G), is the minimum cardinality of a set S subset of V (G) such that every vertex w is an element of E V (G) \ S has two distinct neighbors u, v is an element of S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S. In this work, first we provide bounds on in(cc) (G) and its relations to other graph convexity parameters, and explore its behaviour on grids. Then, we present some hardness results by showing that deciding whetherin(cc) (G) <= k is NPcomplete, even if G is a split graph or a boundeddegree planar graph, and that the problem is W[2]hard in bipartite graphs when k is the parameter. As a consequence, we obtain that in(cc) (G) cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = NP). On the positive side, we present polynomialtime algorithms to compute in(cc) (G) for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixedparameter tractable (FPT) algorithms to compute it for (q, q – 4)graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G. Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomialtime algorithms can be helpful in order to advance in the study of related graph problems.



Becker, F., Montealegre, P., Rapaport, I., & Todinca, I. (2021). The role of randomness in the broadcast congested clique model. Inf. Comput., 281, 104669.
Abstract: We study the role of randomness in the broadcast congested clique model. This is a messagepassing model of distributed computation where the nodes of a network know their local neighborhoods and they broadcast, in synchronous rounds, messages that are visible to every other node.
This works aims to separate three different settings: deterministic protocols, randomized protocols with private coins, and randomized protocols with public coins. We obtain the following results:
If more than one round is allowed, public randomness is as powerful as private randomness.
Oneround publiccoin algorithms can be exponentially more powerful than deterministic algorithms running in several rounds.
Oneround publiccoin algorithms can be exponentially more powerful than oneround privatecoin algorithms.
Oneround privatecoin algorithms can be exponentially more powerful than oneround deterministic algorithms.



Bitar, N., Goles, E., & Montealegre, P. (2022). COMPUTATIONAL COMPLEXITY OF BIASED DIFFUSIONLIMITED AGGREGATION. SIAM Discret. Math., 36(1), 823–866.
Abstract: DiffusionLimited Aggregation (DLA) is a clustergrowth model that consists in a set of particles that are sequentially aggregated over a twodimensional grid. In this paper, we introduce a biased version of the DLA model, in which particles are limited to move in a subset of possible directions. We denote by kDLA the model where the particles move only in k possible directions. We study the biased DLA model from the perspective of Computational Complexity, defining two decision problems The first problem is Prediction, whose input is a site of the grid c and a sequence S of walks, representing the trajectories of a set of particles. The question is whether a particle stops at site c when sequence S is realized. The second problem is Realization, where the input is a set of positions of the grid, P. The question is whether there exists a sequence S that realizes P, i.e. all particles of S exactly occupy the positions in P. Our aim is to classify the Prediciton and Realization problems for the different versions of DLA. We first show that Prediction is PComplete for 2DLA (thus for 3DLA). Later, we show that Prediction can be solved much more efficiently for 1DLA. In fact, we show that in that case the problem is NLComplete. With respect to Realization, we show that restricted to 2DLA the problem is in P, while in the 1DLA case, the problem is in L.



Fomin, F. V., Golovach, P. A., Kratochvil, J., Nisse, N., & Suchan, K. (2010). Pursuing a fast robber on a graph. Theor. Comput. Sci., 411(79), 1167–1181.
Abstract: The Cops and Robbers game as originally defined independently by Quilliot and by Nowakowski and Winkler in the 1980s has been Much Studied, but very few results pertain to the algorithmic and complexity aspects of it. In this paper we prove that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is NPhard and that the parameterized version of the problem is W[2]hard; the proof extends to the case where the robber moves s time faster than the cops. We show that on split graphs, the problem is polynomially solvable if s = 1 but is NPhard if s = 2. We further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for s <= 2. Finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops. (C) 2009 Elsevier B.V. All rights reserved.



Formenti, E., Goles, E., & Martin, B. (2012). Computational Complexity of Avalanches in the Kadanoff Sandpile Model. Fundam. Inform., 115(1), 107–124.
Abstract: This paper investigates the avalanche problem AP for the Kadanoff sandpile model (KSPM). We prove that (a slight restriction of) AP is in NC1 in dimension one, leaving the general case open. Moreover, we prove that AP is Pcomplete in dimension two. The proof of this latter result is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with an initial sand distribution in KSPM. These results are also related to the known prediction problem for sandpiles which is in NC1 for onedimensional sandpiles and Pcomplete for dimension 3 or higher. The computational complexity of the prediction problem remains open for the Bak's model of twodimensional sandpiles.



Gajardo, A., & Goles, E. (2006). Crossing information in twodimensional Sandpiles. Theor. Comput. Sci., 369(13), 463–469.
Abstract: We prove that in a twodimensional Sandpile automaton, embedded in a regular infinite planar cellular space, it is impossible to cross information, if the bit of information is the presence (or absence) of an avalanche. This proves that it is impossible to embed arbitrary logical circuits in a Sandpile through quiescent configurations. Our result applies also for the nonplanar neighborhood of Moore. Nevertheless, we also show that it is possible to compute logical circuits with a twodimensional Sandpile, if a neighborhood of radius two is used in Z(2); crossing information becomes possible in that case, and we conclude that for this neighborhood the Sandpde is Pcomplete and Turing universal. (c) 2006 Elsevier B.V. All rights reserved.



Gaspers, S., Liedloff, M., Stein, M., & Suchan, K. (2015). Complexity of splits reconstruction for lowdegree trees. Discret Appl. Math., 180, 89–100.
Abstract: Given a vertexweighted tree T, the split of an edge em T is the minimum over the weights of the two trees obtained by removing e from T, where the weight of a tree is the sum of weights of its vertices. Given a set of weighted vertices V and a multiset of integers s, we consider the problem of constructing a tree on V whose splits correspond to s. The problem is known to be NPcomplete, even when all vertices have unit weight and the maximum vertex degree of T is required to be at most 4. We show that the problem is strongly NPcomplete when T is required to be a path, the problem is NPcomplete when all vertices have unit weight and the maximum degree of T is required to be at most 3, and it remains NPcomplete when all vertices have unit weight and T is required to be a caterpillar with unbounded hair length and maximum degree at most 3. We also design polynomial time algorithms for the variant where T is required to be a path and the number of distinct vertex weights is constant, and the variant where all vertices have unit weight and T has a constant number of leaves. The latter algorithm is not only polynomial when the number of leaves, k, is a constant, but also is a fixedparameter algorithm for parameter k. Finally, we shortly discuss the problem when the vertex weights are not given but can be freely chosen by an algorithm. The considered problem is related to building libraries of chemical compounds used for drug design and discovery. In these inverse problems, the goal is to generate chemical compounds having desired structural properties, as there is a strong relation between structural invariants of the particles, such as the Wiener index and, less directly, the problem under consideration here, and physicochemical properties of the substance. (C) 2014 Elsevier B.V. All rights reserved.



Goles, E., & Montealegre, P. (2014). Computational complexity of threshold automata networks under different updating schemes. Theor. Comput. Sci., 559, 3–19.
Abstract: Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the ANDOR rule (vertices take the AND or the OR logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs. (C) 2014 Elsevier B.V. All rights reserved.



Goles, E., & Montealegre, P. (2015). The complexity of the majority rule on planar graphs. Adv. Appl. Math., 64, 111–123.
Abstract: We study the complexity of the majority rule on planar automata networks. We reduce a special case of the Monotone Circuit Value Problem to the prediction problem of determining if a vertex of a planar graph will change its state when the network is updated with the majority rule. (C) 2014 Elsevier Inc. All rights reserved.



Goles, E., & Montealegre, P. (2020). The complexity of the asynchronous prediction of the majority automata. Inf. Comput., 274(SI).
Abstract: We consider the asynchronous prediction problem for some automaton as the one consisting in determining, given an initial configuration, if there exists a nonzero probability that some selected site changes its state, when the network is updated picking one site at a time uniformly at random. We show that for the majority automaton, the asynchronous prediction problem is in NC in the twodimensional lattice with von Neumann neighborhood. Later, we show that in three or more dimensions the problem is NPComplete.



Goles, E., & Moreira, A. (2012). NumberConserving Cellular Automata and Communication Complexity: A Numerical Exploration Beyond Elementary CAs. J. Cell. Autom., 7(2), 151–165.
Abstract: We perform a numerical exploration of numberconserving cellular automata (NCCA) beyond the class of elementary CAs, in search of examples with high communication complexity. We consider some possible generalizations of the elementary rule 184 (a minimal model of traffic, which is the only nontrivial elementary NCCA). as well as the classes of NCCAs which minimally extend either the radius or the state set (with respect to the 2 states and radius 1 of the elementary case). Both for 3 states and radius 1, and for 2 stales and radius 2, NCCA appear that are conjectured to have maximal (exponential) communication complexity. Examples are given also for (conjectured) linear and quadratic behaviour.



Goles, E., & Palacios, A. G. (2007). Dynamical complexity in cognitive neural networks. Biol. Res., 40(4), 479–485.
Abstract: In the last twenty years an important effort in brain sciences, especially in cognitive science, has been the development of mathematical tool that can deal with the complexity of extensive recordings corresponding to the neuronal activity obtained from hundreds of neurons. We discuss here along with some historical issues, advantages and limitations of Artificial Neural Networks (ANN) that can help to understand how simple brain circuits work and whether ANN can be helpful to understand brain neural complexity.



Goles, E., Adamatzky, A., Montealegre, P., & RiosWilson, M. (2021). Generating Boolean Functions on Totalistic Automata Networks. Int. J. Unconv. Comput., 16(4), 343–391.
Abstract: We consider the problem of studying the simulation capabilities of the dynamics of arbitrary networks of finite states machines. In these models, each node of the network takes two states 0 (passive) and 1 (active). The states of the nodes are updated in parallel following a local totalistic rule, i.e., depending only on the sum of active states. Four families of totalistic rules are considered: linear or matrix defined rules (a node takes state 1 if each of its neighbours is in state 1), threshold rules (a node takes state 1 if the sum of its neighbours exceed a threshold), isolated rules (a node takes state 1 if the sum of its neighbours equals to some single number) and interval rule (a node takes state 1 if the sum of its neighbours belong to some discrete interval). We focus in studying the simulation capabilities of the dynamics of each of the latter classes. In particular, we show that totalistic automata networks governed by matrix defined rules can only implement constant functions and other matrix defined functions. In addition, we show that t by threshold rules can generate any monotone Boolean functions. Finally, we show that networks driven by isolated and the interval rules exhibit a very rich spectrum of boolean functions as they can, in fact, implement any arbitrary Boolean functions. We complement this results by studying experimentally the set of different Boolean functions generated by totalistic rules on random graphs.



Goles, E., Guillon, P., & Rapaport, I. (2011). Traced communication complexity of cellular automata. Theor. Comput. Sci., 412(30), 3906–3916.
Abstract: We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansivity, entropy and give the asymptotic communication complexity of most elementary cellular automata. (C) 2011 Elsevier B.V. All rights reserved.



Goles, E., Lobos, F., Montealegre, P., Ruivo, E. L. P., & de Oliveira, P. P. B. (2020). Computational Complexity of the Stability Problem for Elementary Cellular Automata. J. Cell. Autom., 15(4), 261–304.
Abstract: Given an elementary cellular automaton and a cell v, we define the stability decision problem as the determination of whether or not the state of cell v will ever change, at least once, during the time evolution of the rule, over a finite input configuration. Here, we perform the study of the entire elementary cellular automata rule space, for the two possible decision cases of the problem, namely, changes in v from state 0 to 1 (0 > 1), and the other way round (1 > 0). Out of the 256 elementary cellular automata, we show that for all of them, at least one of the two decision problems is in the NC complexity class.



Goles, E., Maldonado, D., & Montealecre, P. (2021). On the complexity of asynchronous freezing cellular automata. Inf. Comput., 281, 104764.
Abstract: In this paper we study the family of freezing cellular automata (FCA) in the context of asynchronous updating schemes. A cellular automaton is called freezing if there exists an order of its states, and the transitions are only allowed to go from a lower to a higher state. A cellular automaton is asynchronous if at each timestep only one cell is updated. We define the problem ASYNCUNSTABILITY, which consists in deciding there exists a sequential updating scheme that changes the state of a given cell.
We begin showing that ASYNCUNSTABILITY is in NL for any onedimensional FCA. Then we focus on the family of lifelike freezing CA (LFCA). We study the complexity of ASYNCUNSTABILITY for all LFCA in the triangular and square grids, showing that almost all of them can be solved in NC, except for one rule for which the problem is NPComplete. (C) 2021 Elsevier Inc. All rights reserved.



Goles, E., Maldonado, D., Montealegre, P., & Ollinger, N. (2020). On the complexity of the stability problem of binary freezing totalistic cellular automata. Inf. Comput., 274, 21 pp.
Abstract: In this paper we study the family of twostate Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only on the sum of its active neighbors. We classify all the Cellular Automata in the class of TFCA, grouping them in five different classes: the Trivial rules, Turing Universal rules, Algebraic rules, Topological rules and Fractal Growing rules. At the same time, we study in this family the STABILITY problem, consisting in deciding whether an inactive cell becomes active, given an initial configuration. We exploit the properties of the automata in each group to show that: For Algebraic and Topological Rules the STABILITY problem is in NC. For Turing Universal rules the STABILITY problem is PComplete. (C) 2020 Elsevier Inc. All rights reserved.



Goles, E., Meunier, P. E., Rapaport, I., & Theyssier, G. (2011). Communication complexity and intrinsic universality in cellular automata. Theor. Comput. Sci., 412(12), 2–21.
Abstract: The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains hard in most cases. In this article, we introduce necessary conditions for a cellular automaton to be “universal”, according to a precise notion of simulation, related both to the dynamics of cellular automata and to their computational power. This notion of simulation relies on simple operations of spacetime rescaling and it is intrinsic to the model of cellular automata. intrinsic universality, the derived notion, is stronger than Turing universality, but more uniform, and easier to define and study. Our approach builds upon the notion of communication complexity, which was primarily designed to study parallel programs, and thus is, as we show in this article, particulary well suited to the study of cellular automata: it allowed us to show, by studying natural problems on the dynamics of cellular automata, that several classes of cellular automata, as well as many natural (elementary) examples, were not intrinsically universal. (C) 2010 Elsevier B.V. All rights reserved.



Goles, E., MontalvaMedel, M., Montealegre, P., & RiosWilson, M. (2022). On the complexity of generalized Q2R automaton. Adv. Appl. Math., 138, 102355.
Abstract: We study the dynamic and complexity of the generalized Q2R automaton. We show the existence of nonpolynomial cycles as well as its capability to simulate with the synchronous update the classical version of the automaton updated under a block sequential update scheme. Furthermore, we show that the decision problem consisting in determine if a given node in the network changes its state is PHard.

