Thiago Braga Marcilon

dblp:133/8742 · also Thiago Marcilon · DBLP profile ↗
← Back
14ranked-venue papers
7as first author
7since 2021 · last 2026
0000-0002-9302-9405ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 14 · 7 first-author · 7 since 2021Databases, data management, data science and information retrieval · 2 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2026 The conversion set problem on graphs
abstract
Given a graph G = ( V , E ) and a threshold function f : V ( G ) → N , an f -reversible process on G is a dynamical system such that, given an initial vertex labeling c 0 : V ( G ) → { 0,1 } , every vertex v changes its label if and only if it has at least f ( v ) neighbors with the opposite label, synchronously in discrete-time steps. An f -conversion set of G is a subset of vertices of G with initial label equal to 1 such that, in an f -reversible process on G , eventually, all vertices reach label 1 and it does not get changed anymore. The conversion set number r f ( G ) is the minimum cardinality of an f -conversion set of G . The Conversion Set Problem asks whether r f ( G ) ≤ k , which is known to be NP -complete. We prove that it is W [1]-hard when parameterized by the treewidth of G and k together by showing a parameterized reduction from Target Set Selection with the same parameters. We also show a polynomial-time algorithm to determine r f ( P ) for any path P , a problem which has been left open for over ten years. We also consider a quite similar version on an orientation D = ( V , E ⃗ ) of a graph G = ( V , E ) , that is, an oriented graph obtained from G by choosing one orientation for each edge of G . In this version, a vertex v changes its label if and only if it has at least f ( v ) incoming neighbors with opposite label. We prove the W [2]-hardness of the Conversion Set Problem for this version parameterized by k , even for an orientation with only one directed cycle and all thresholds equal to 1, and a linear-time algorithm for acyclic orientations.
Isac Costa, Carlos V. G. C. Lima, Thiago Braga Marcilon
Discret. Appl. Math.3
2026 Parameterized complexity of the f -Critical Set problem
Thiago Braga Marcilon, Murillo Inácio da Costa Silva
Discret. Appl. Math.1
2026 The harmonious coloring game
Cláudia Linhares Sales, Thiago Braga Marcilon, Nicolas Almeida Martins, Nicolas Nisse, Rudini Menezes Sampaio
Inf. Process. Lett.2
2026 The Normal Domination Game in graphs
João Marcos Brito, Thiago Braga Marcilon, Nicolas Almeida Martins, Rudini Menezes Sampaio
J. Comput. Syst. Sci.2
2023 The Conversion Set Problem on Graphs
Isac Costa, Carlos V. G. C. Lima, Thiago Braga Marcilon
LAGOS3
2023 The connected greedy coloring game
Carlos V. G. C. Lima, Thiago Braga Marcilon, Nicolas Almeida Martins, Rudini Menezes Sampaio
Theor. Comput. Sci.2
2022 PSPACE-hardness of variants of the graph coloring game
Carlos V. G. C. Lima, Thiago Braga Marcilon, Nicolas Almeida Martins, Rudini Menezes Sampaio
Theor. Comput. Sci.2
2020 Hardness of Variants of the Graph Coloring Game
Thiago Braga Marcilon, Nicolas Almeida Martins, Rudini Menezes Sampaio
LATIN1
2019 On the parameterized complexity of the geodesic hull number
Mamadou Moustapha Kanté, Thiago Braga Marcilon, Rudini Menezes Sampaio
Theor. Comput. Sci.2
2018 The maximum infection time of the P3 convexity in graphs with bounded maximum degree
Thiago Braga Marcilon, Rudini Menezes Sampaio
Discret. Appl. Math.1
2018 The P3 infection time is W[1]-hard parameterized by the treewidth
Thiago Braga Marcilon, Rudini Menezes Sampaio
Inf. Process. Lett.1
2018 The maximum time of 2-neighbor bootstrap percolation: Complexity results
Thiago Braga Marcilon, Rudini Menezes Sampaio
Theor. Comput. Sci.1
2015 The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results
Thiago Braga Marcilon, Rudini Menezes Sampaio
WG1
2014 The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
Thiago Braga Marcilon, Samuel N. Araújo, Rudini Menezes Sampaio
WG1