On the Harmless Set Problem Parameterized by Treewidth

Abstract

Given a graph G=(V,E), a threshold function t : V→N and an integer k, we study the HARMLESS SET problem, where the goal is to find a subset of vertices S⊆V of size at least k such that every vertex v in V has less than t(v) neighbors in S. We enhance our understanding of the problem from the viewpoint of parameterized complexity. Our focus lies on parameters that measure the structural properties of the input instance. We show that the HARMLESS SET problem with majority thresholds is W[1]-hard when parameterized by the treewidth of the input graph. On the positive side, we obtain a fixed-parameter tractable algorithm for the problem with respect to neighbourhood diversity.