On Structural Parameterizations of the Harmless Set Problem

Abstract

In this paper, we study the HARMLESS SET problem from a parameterized complexity perspective. Given a graph G=(V,E), a threshold function t : V -> N and an integer k, we study HARMLESS SET, where the goal is to find a subset of vertices S subset of V of size at least k such that every vertex v is an element of V has fewer than t(v) neighbours in S. On the positive side, we obtain fixed-parameter algorithms for the problem when parameterized by the neighbourhood diversity, the twin-cover number and the vertex integrity of the input graph. We complement two of these results from the negative side. On dense graphs, we show that the problem is W[1]-hard parameterized by cluster vertex deletion number-a natural generalization of the twin-cover number. We show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, and treedepth-a natural generalization of the vertex integrity. We thereby resolve one open question stated by Bazgan and Chopin (Discrete Optim 14(C):170-182, 2014) concerning the complexity of HARMLESS SET parameterized by the treewidth of the input graph. We also show that HARMLESS SET for a special case where each vertex has the threshold set to half of its degree (the so-called MAJORITY HARMLESS SET problem) is W[1]-hard when parameterized by the treewidth of the input graph. Given a graph G and an irredundant c-expression of G, we prove that HARMLESS SET can be solved in XP-time when parameterized by clique-width.