Please use this identifier to cite or link to this item: http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/8209
Title: Parameterized Complexity of the Th+1 -Free Edge Deletion Problem
Fundamentals of Computation Theory
Authors: GAIKWAD, AJINKYA
MAITY, SOUMEN
Dept. of Mathematics
Keywords: Computer Science
2023
2023-SEP-WEEK4
TOC-SEP-2023
Issue Date: Sep-2023
Publisher: Springer Nature
Citation: Fundamentals of Computation Theory, 221–233.
Abstract: Given an undirected graph G=(V,E) and two integers k and h, we study Th+1 -FREE EDGE DELETION, where the goal is to remove at most k edges such that the resulting graph does not contain any tree on h+1 vertices as a (not necessarily induced) subgraph, that is, we delete at most k edges in order to obtain a graph in which every component contains at most h vertices. This is desirable from the point of view of restricting the spread of a disease in transmission networks. Enright and Meeks (Algorithmica, 2018) gave an algorithm to solve Th+1 -FREE EDGE DELETION whose running time on an n-vertex graph G of treewidth tw(G) is bounded by O((tw(G)h)2tw(G)n) . However, it remains open whether the problem might belong to FPT when parameterized only by the treewidth tw(G) ; they conjectured that treewidth alone is not enough, and that the problem is W[1]-hard with respect to this parameterization. We resolve this conjecture by showing that Th+1 -FREE EDGE DELETION is indeed W[1]-hard when parameterized by tw(G) alone. We resolve two additional open questions posed by Enright and Meeks (Algorithmica, 2018) concerning the complexity of Th+1 -FREE EDGE DELETION on planar graphs and Th+1 -FREE ARC DELETION. We prove that the Th+1 -FREE EDGE DELETION problem is NP-complete even when restricted to planar graphs. We also show that the Th+1 -FREE ARC DELETION problem is W[2]-hard when parameterized by the solution size on directed acyclic graphs.
URI: https://link.springer.com/chapter/10.1007/978-3-031-43587-4_16
http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/8209
ISBN: 9783031435867
ISSN: 9783031435874
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.