The Conversion Set Problem on Graphs
Isac Costa, Carlos V. G. C. Lima, Thiago Marcilon · Discrete Applied Mathematics · 2023
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.