Source author record

Thiago Braga Marcilon

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity

Catalog footprint

Research overview

2works

1topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

The maximum time of 2-neighbor bootstrap percolation: complexity results

In 2-neighborhood bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: infected vertices of G remain infected forever and in consecutive rounds healthy vertices with at least 2 already infected neighbors become infected. Percolation occurs if eventually every vertex is infected. The maximum time t(G) is the maximum number of rounds needed to eventually infect the entire vertex set. In 2013, it was proved \cite{eurocomb13} that deciding whether $t(G)\geq k$ is polynomial time solvable for k=2, but is NP-Complete for k=4 and, if the problem is restricted to bipartite graphs, it is NP-Complete for k=7. In this paper, we solve the open questions. We obtain an $O(mn^5)$ -time algorithm to decide whether $t(G)\geq 3$ . For bipartite graphs, we obtain an $O(mn^3)$ -time algorithm to decide whether $t(G)\geq 3$ , an $O(m^2n^9)$ -time algorithm to decide whether $t(G)\geq 4$ and we prove that $t(G)\geq 5$ is NP-Complete.

preprint2015arXiv

The maximum time of 2-neighbour bootstrap percolation in grid graphs and some parameterized results

In 2-neighborhood bootstrap percolation on a graph $G$ , an infection spreads according to the following deterministic rule: infected vertices of $G$ remain infected forever and in consecutive rounds healthy vertices with at least two already infected neighbors become infected. Percolation occurs if eventually every vertex is infected. The maximum time $t(G)$ is the maximum number of rounds needed to eventually infect the entire vertex set. In 2013, it was proved by Benevides et al \cite{eurocomb13} that $t(G)$ is NP-hard for planar graphs and that deciding whether $t(G)\geq k$ is polynomial time solvable for $k\leq 2$ , but is NP-complete for $k\geq 4$ . They left two open problems about the complexity for $k=3$ and for planar bipartite graphs. In 2014, we solved the first problem\cite{wg2014}. In this paper, we solve the second one by proving that $t(G)$ is NP-complete even in grid graphs with maximum degree 3. We also prove that $t(G)$ is polynomial time solvable for solid grid graphs with maximum degree 3. Moreover, we prove that the percolation time problem is W[1]-hard on the treewidth of the graph, but it is fixed parameter tractable with parameters treewidth $+k$ and maxdegree $+k$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.