Parameterized complexity of the f -Critical Set problem

Given a graph G= (V, E), and a function f: V (G) N, an f-reversible process on G is a dynamical system such that, given an initial vertex labeling c₀: 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. The updates occur synchronously in discrete time steps t=0, 1, 2,. An f-critical set of G is a subset of vertices of G whose initial label is 1 such that, in an f-reversible process on G, all vertices reach label 1 within one time step and then remain unchanged. The critical set number rᶜf (G) is the minimum size of an f-critical set of G. Given a graph G, a threshold function f, and an integer k, the f-Critical Set problem asks whether rᶜf (G) k. We prove that this problem is NP-complete for planar subcubic bipartite graphs with maximum threshold m (f) = 2 and W1-hard when parameterized by the treewidth tw (G) of G. Additionally, we show that the problem is FPT when parameterized by tw (G) +m (f), tw (G) +Δ (G), and k, where Δ (G) denotes the maximum degree of G. Finally, we present two kernels of sizes O (k m (f) ) and O (k Δ (G) ).