2026-07-23T19:43:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8412 2024-03-06T10:41:55Z ddc:004 open_access

On the Parameterized Complexity of Simultaneous Deletion Problems Agrawal, Akanksha Krithika, R. Lokshtanov, Daniel Mouawad, Amer E. Ramanujan, M. S. parameterized complexity feedback vertex set odd cycle transversal edge-colored graphs simultaneous deletion For a family of graphs F, an n-vertex graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A (multi) graph G = (V, \cup_{i=1}^{\alpha} E_{i}), where the edge set of G is partitioned into \alpha color classes, is called an \alpha-edge-colored graph. A natural extension of the F-Deletion problem to edge-colored graphs is the Simultaneous (F_1, \ldots, F_\alpha)-Deletion problem. In the latter problem, we are given an \alpha-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph G_i - S, where G_i = (V, E_i) and 1 \leq i \leq \alpha, is in F_i. Recently, a subset of the authors considered the aforementioned problem with F_1 = \ldots = F_\alpha being the family of all forests. They showed that the problem is fixed-parameter tractable when parameterized by k and \alpha, and can be solved in O(2^{O(\alpha k)}n^{O(1)}) time. In this work, we initiate the investigation of the complexity of Simultaneous (F_1, \ldots, F_\alpha)-Deletion with different families of graphs. In the process, we obtain a complete characterization of the parameterized complexity of this problem when one or more of the F_i's is the class of bipartite graphs and the rest (if any) are forests. We show that if F_1 is the family of all bipartite graphs and each of F_2 = F_3 = \ldots = F_\alpha is the family of all forests then the problem is fixed-parameter tractable parameterized by k and \alpha. However, even when F_1 and F_2 are both the family of all bipartite graphs, then the Simultaneous (F_1, F_2)-Deletion} problem itself is already W[1]-hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akanksha Agrawal and R. Krithika and Daniel Lokshtanov and Amer E. Mouawad and M. S. Ramanujan 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.9 urn:nbn:de:0030-drops-84128 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.9 eng https://creativecommons.org/licenses/by/3.0/legalcode