Isac Costa

dblp:365/5005 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2026
—ORCID · none

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

Theory of computation · 2 · 2 first-author · 2 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.1
2023 The Conversion Set Problem on Graphs
Isac Costa, Carlos V. G. C. Lima, Thiago Braga Marcilon
LAGOS1