2026-08-10T07:42:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5708 2024-03-06T10:36:53Z ddc:004 open_access

Simultaneous Feedback Vertex Set: A Parameterized Perspective Agrawal, Akanksha Lokshtanov, Daniel Mouawad, Amer E. Saurabh, Saket parameterized complexity ,feedback vertex set kernel edge-colored graphs For a family of graphs F, a 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 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 alpha-SIMULTANEOUS F-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 <= i <= alpha, is in F. In this work, we study alpha-SIMULTANEOUS F-DELETION for F being the family of forests. In other words, we focus on the alpha-SIMULTANEOUS FEEDBACK VERTEX SET (alpha-SIMFVS) problem. Algorithmically, we show that, like its classical counterpart, alpha-SIMFVS parameterized by k is fixed-parameter tractable (FPT) and admits a polynomial kernel, for any fixed constant alpha. In particular, we give an algorithm running in 2^{O(alpha * k)} * n^{O(1)} time and a kernel with O(alpha * k^{3(alpha + 1)}) vertices. The running time of our algorithm implies that alpha-SIMFVS is FPT even when alpha in o(log(n)). We complement this positive result by showing that for alpha in O(log(n)), where n is the number of vertices in the input graph, alpha-SIMFVS becomes W[1]-hard. Our positive results answer one of the open problems posed by Cai and Ye (MFCS 2014). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akanksha Agrawal and Daniel Lokshtanov and Amer E. Mouawad and Saket Saurabh 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.7 urn:nbn:de:0030-drops-57084 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.7 eng https://creativecommons.org/licenses/by/3.0/legalcode