Simultaneous Feedback Edge Set: A Parameterized Perspective
- PDF / 1,998,339 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 1 Downloads / 207 Views
Simultaneous Feedback Edge Set: A Parameterized Perspective Akanksha Agrawal1,2 · Fahad Panolan1,3 · Saket Saurabh4 · Meirav Zehavi1,2 Received: 15 November 2019 / Accepted: 24 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Agrawal et al. (ACM Trans Comput Theory 10(4):18:1–18:25, 2018. https://doi. org/10.1145/3265027) studied a simultaneous variant of the classic Feedback Vertex Set problem, called Simultaneous Feedback Vertex Set (Sim-FVS). Here, we consider the edge variant of the problem, namely, Simultaneous Feedback Edge Set (Sim-FES). In this problem, the input is an n-vertex graph G, a positive integer k, and a coloring function col:E(G) → 2[𝛼] , and the objective is to check whether there is an edge subset S of cardinality k in G such that for each i ∈ [𝛼] , Gi − S is acyclic. Unlike the vertex variant of the problem, when 𝛼 = 1 , the problem is equivalent to finding a maximal spanning forest and hence it is polynomial time solvable. We show that for 𝛼 = 3 , Sim-FES is NP-hard, and does not admit an algorithm of running time 2o(k) nO(1) unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time 2𝜔k𝛼+𝛼 log k nO(1) where 𝜔 is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when 𝛼 = 2 . We also give a kernel for Sim-FES with (k𝛼)O(𝛼) vertices. Finally, we consider a “dual” version of the problem called Maximum Simultaneous Acyclic Subgraph and give an FPT algorithm with running time 2𝜔q𝛼 nO(1) , where q is the number of edges in the output subgraph. Keywords Parameterized complexity · Feedback edge set · 𝛼-matroid parity
A preliminary version of this paper appeared in the proceedings of the 27th International Symposium Algorithms and Computation (ISAAC 2016). The research leading to these results has received funding from the European Research Council (ERC) via grants Rigorous Theory of Preprocessing, reference 267959 and PARAPPROX, reference 306992. * Fahad Panolan [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
1 Introduction Deleting at most k vertices or edges from a given graph G, so that the resulting F graph belongs to a particular family of graphs ( ), is an important research direction in the fields of graph algorithms and parameterized complexity. For a family of graphs F , given a graph G and an integer k, the F -deletion (Edge F -deletion) problem asks whether we can delete at most k vertices (edges) in G so that the resulting graph belongs to F . The F -deletion (Edge F -deletion) problems generalize many of the NP-hard problems like Vertex Cover, Feedback vertex set, Odd cycle transversal, Edge Bipartization, etc. Inspired by applications, Cai and Ye introduced variants of F -deletion (Edge F -deletion) on edge colored graphs [3]. One of the natural generalizations to the classic F -deletion (Edge F -deletion) problems on edge colored graphs
Data Loading...
