Agrawal, Akanksha and Panolan, Fahad and Saurabh, Saket and et al, .
(2021)
Simultaneous Feedback Edge Set: A Parameterized Perspective.
Algorithmica, 83 (2).
pp. 753774.
ISSN 01784617
Full text not available from this repository.
(
Request a copy)
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 (SimFVS). Here, we consider the edge variant of the problem, namely, Simultaneous Feedback Edge Set (SimFES). In this problem, the input is an nvertex 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 , SimFES is NPhard, and does not admit an algorithm of running time 2 o(k)nO(1) unless ETH fails. This hardness result is complimented by an FPT algorithm for SimFES running in time 2 ωkα+αlogknO(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 SimFES 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. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.
[error in script]
Actions (login required)

View Item 