Simultaneous Feedback Edge Set: A Parameterized Perspective

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)


Agrawal et al. (ACM Trans Comput Theory 10(4):18:1–18:25, 2018. 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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Panolan, Fahad
Item Type: Article
Additional Information: 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.
Uncontrolled Keywords: Feedback edge set; Parameterized complexity; α-matroid parity
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 26 Sep 2022 08:45
Last Modified: 26 Sep 2022 08:45
Publisher URL:
OA policy:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 10708 Statistics for this ePrint Item