2015/10/06 by Akanksha Agrawal, Agrawal, Akanksha, Daniel Lokshtanov +5
Computer Science · Engineering · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.1510.01557
openalex publication_date 2015/10/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given 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, ∪i=1α Ei), where the edge set of G is partitioned into α color classes, is called an α-edge-colored graph. A natural extension of the F-Deletion problem to edge-colored graphs is the α-Simultaneous F-Deletion problem. In the latter problem, we are given an α-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph Gi ∖ S, where Gi = (V, Ei) and 1 ≤ i ≤ α, is in F. In this work, we study α-Simultaneous F-Deletion for F being the family of forests. In other words, we focus on the α-Simultaneous Feedback Vertex Set (α-SimFVS) problem. Algorithmically, we show that, like its classical counterpart, α-SimFVS parameterized by k is fixed-parameter tractable (FPT) and admits a polynomial kernel, for any fixed constant α. In particular, we give an algorithm running in 2O(αk)nO(1) time and a kernel with O(αk3(α+ 1)) vertices. The running time of our algorithm implies that α-SimFVS is FPT even when α∈ o(log n). We complement this positive result by showing that for α∈ O(log n), where n is the number of vertices in the input graph, α-SimFVS becomes W[1]-hard. Our positive results answer one of the open problems posed by Cai and Ye (MFCS 2014).