Please use this identifier to cite or link to this item:
http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/6631| Title: | On the Harmless Set Problem Parameterized by Treewidth |
| Authors: | GAIKWAD, AJINKYA MAITY, SOUMEN Mutzel, Petra Rahman, Md. Saidur Slamin Dept. of Mathematics |
| Keywords: | 2022-MAR-WEEK3 TOC-MAR-2022 2022 Parameterized Complexity FPT W[1]-hard Treewidth |
| Issue Date: | Mar-2022 |
| Publisher: | Springer Nature |
| Citation: | WALCOM: Algorithms and Computation, 227–238. |
| 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. |
| URI: | https://doi.org/10.1007/978-3-030-96731-4_19 http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/6631 |
| Appears in Collections: | BOOK CHAPTERS |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.