Parameterized complexity of the f-Critical Set problem

Abstract

Given a graph $G=(V,E)$, and a function $f:V(G)\to \mathbb{N}$, an $f$-reversible process on $G$ is a dynamical system such that, given an initial vertex labeling $c_0:V(G)\to \{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,\dots$. 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^c(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^c(G)\le k$. We prove that this problem is NP-complete for planar subcubic bipartite graphs with maximum threshold $m(f)=2$ and W[1]-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)+\Delta (G)$, and $k$, where $\Delta (G)$ denotes the maximum degree of $G$. Finally, we present two kernels of sizes $O(k\cdot m(f))$ and $O(k\cdot \Delta (G))$.

19 pages, 6 figures, 1 table

References in corpus (1)

• An energy function and its application to the periodic behavior of k-reversible processes