Agrawal, Akanksha and Panolan, Fahad and Saurabh, Saket and et al, .
(2021)
Simultaneous Feedback Edge Set: A Parameterized Perspective.
Algorithmica, 83 (2).
pp. 753-774.
ISSN 0178-4617
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 (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 2 o(k)nO(1) unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES 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 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. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.
Actions (login required)
 |
View Item |
Altmetric
Altmetric