License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.9
URN: urn:nbn:de:0030-drops-84128
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8412/
Agrawal, Akanksha ;
Krithika, R. ;
Lokshtanov, Daniel ;
Mouawad, Amer E. ;
Ramanujan, M. S.
On the Parameterized Complexity of Simultaneous Deletion Problems
Abstract
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.
BibTeX - Entry
@InProceedings{agrawal_et_al:LIPIcs:2018:8412,
author = {Akanksha Agrawal and R. Krithika and Daniel Lokshtanov and Amer E. Mouawad and M. S. Ramanujan},
title = {{On the Parameterized Complexity of Simultaneous Deletion Problems}},
booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
pages = {9:1--9:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-055-2},
ISSN = {1868-8969},
year = {2018},
volume = {93},
editor = {Satya Lokam and R. Ramanujam},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8412},
URN = {urn:nbn:de:0030-drops-84128},
doi = {10.4230/LIPIcs.FSTTCS.2017.9},
annote = {Keywords: parameterized complexity, feedback vertex set, odd cycle transversal, edge-colored graphs, simultaneous deletion}
}
|
Keywords: |
|
parameterized complexity, feedback vertex set, odd cycle transversal, edge-colored graphs, simultaneous deletion |
|
Collection: |
|
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
12.02.2018 |
