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.

A target set selection model is a graph G with a threshold function τ : V(G) → N upper-bounded by the vertex degree. For a given model, a set S0 ⊆ V(G) is a target set if V(G) can be partitioned into non-empty subsets S0, S1,....,St such that, for all i∈{1,....,t}, Si contains exactly every vertex v having at least τ(v) neighbors in S0∪⋯∪Si−1. We say that t is the activation time tτ(S0) of the target set S0. The problem of, given such a model, finding a target set of minimum size has been extensively studied in the literature. In this article, we investigate its variant, which we call TSS-time, in which the goal is to find a target set S0 that maximizes tτ(S0). That is, given a graph G, a threshold function τ in G, and an integer k, the objective of the TSS-time problem is to decide whether G contains a target set S0 such that tτ(S0)≥k. Let τ*=maxV∈V(G)τ(v). Our main result is the following dichotomy about the complexity of TSS-time when G belongs to a minor-closed graph class C: if C has bounded local treewidth, the problem is FPT parameterized by k and τ*; otherwise, it is NP-complete even for fixed k = 4 and τ* = 2. We also prove that, with τ = 2, the problem is NP-hard in bipartite graphs for fixed k = 5, and from previous results we observe that TSS-time is NP-hard in planar graphs and W[1]-hard parameterized by treewidth. Finally, we present a linear-time algorithm to find a target set S0 in a given tree maximizing tτ(S0).

Given a graph G, a properk-coloring of G is a partition $$c = (S_i)_{i\in [1,k]}$$ of V(G) into k stable sets $$S_1,\ldots , S_{k}$$ . Given a weight function $$w: V(G) \rightarrow {\mathbb {R}}^+$$ , the weight of a color $$S_i$$ is defined as $$w(i) = \max _{v \in S_i} w(v)$$ and the weight of a coloringc as $$w(c) = \sum _{i=1}^{k}w(i)$$ . Guan and Zhu (Inf Process Lett 61(2):77–81, 1997) defined the weighted chromatic number of a pair (G, w), denoted by $$\sigma (G,w)$$ , as the minimum weight of a proper coloring of G. The problem of determining $$\sigma (G,w)$$ has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time $$n^{o(\log n)}$$ unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G, w) and an integer k, is $$\sigma (G,w) \le \sum _{v \in V(G)} w(v) - k$$ ? This parameterization has been recently considered by Escoffier (in: Proceedings of the 42nd international workshop on graph-theoretic concepts in computer science (WG). LNCS, vol 9941, pp 50–61, 2016), who provided an FPT algorithm running in time $$2^{{\mathcal {O}}(k \log k)} \cdot n^{{\mathcal {O}}(1)}$$ , and asked which kernel size can be achieved for the problem. We provide an FPT algorithm in time $$9^k \cdot n^{{\mathcal {O}}(1)}$$ , and prove that no algorithm in time $$2^{o(k)} \cdot n^{{\mathcal {O}}(1)}$$ exists under the ETH. On the other hand, we present a kernel with at most $$(2^{k-1}+1) (k-1)$$ vertices, and rule out the existence of polynomial kernels unless $$\mathsf{NP} \subseteq \mathsf{coNP} / \mathsf{poly}$$ , even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c = (S_i)_{i\in [1,k]}$ of $V(G)$ into $k$ stable sets $S_1,\ldots, S_{k}$. Given a weight function $w: V(G) \to \mathbb{R}^+$, the weight of a color $S_i$ is defined as $w(i) = \max_{v \in S_i} w(v)$ and the weight of a coloring $c$ as $w(c) = \sum_{i=1}^{k}w(i)$. Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair $(G,w)$, denoted by $\sigma(G,w)$, as the minimum weight of a proper coloring of $G$. The problem of determining $\sigma(G,w)$ has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on $n$-vertex trees in time $n^{o(\log n)}$ unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. In this article we provide some positive results for the problem, by considering its so-called dual parameterization: given a vertex-weighted graph $(G,w)$ and an integer $k$, the question is whether $\sigma(G,w) \leq \sum_{v \in V(G)} w(v) - k$. We prove that this problem is FPT by providing an algorithm running in time $9^k \cdot n^{O(1)}$, and it is easy to see that no algorithm in time $2^{o(k)} \cdot n^{O(1)}$ exists under the ETH. On the other hand, we present a kernel with at most $(2^{k-1}+1) (k-1)$ vertices, and we rule out the existence of polynomial kernels unless ${\sf NP} \subseteq {\sf coNP} / {\sf poly}$, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.