VLDB 2026 Research / reviewers in the wild / expert
Thiago Braga Marcilon
dblp:133/8742 · also Thiago Marcilon
· DBLP profile ↗
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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | The conversion set problem on graphsabstractGiven 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 |
LAGOS | 3 |
| 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 |
LATIN | 1 |
| 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 |
WG | 1 |
| 2014 | The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
Thiago Braga Marcilon, Samuel N. Araújo, Rudini Menezes Sampaio |
WG | 1 |