[Zurück]

M. S. Ramanujan:
"A Faster Parameterized Algorithm for Group Feedback Edge Set";
Vortrag: International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Istanbul, Türkei; 22.06.2016 - 24.06.2016; in: "Graph-Theoretic Concepts in Computer Science", (2016), ISBN: 978-3-662-53535-6; S. 269 - 281.

In the Group Feedback Edge Set (l) (GFES(l)) problem, the input is a group-labeled graph G over a group of order l and an integer k and the objective is to test whether there exists a set of at most k edges intersecting every non-null cycle in G.

The study of the parameterized complexity of GFES(l) was motivated by the fact that it generalizes the classical Edge Bipartization problem when l=2.
Guillemot [IWPEC 2008, Discrete Optimization 2011] initiated the study of the parameterized complexity of this problem and proved that it is fixed-parameter tractable (FPT) parameterized by k. Subsequently, Wahlström [SODA 2014] and Iwata et al. [2014] presented algorithms running in time $O(4^k n^{O(1)})$ (even in the oracle access model) and $O(l^{2k}m) respectively.
In this paper, we give an algorithm for GFES(l) running in time O(4^kk^{3}l(m+n)). Our algorithm matches that of Iwata et al. when l=2 (upto a multiplicative factor of $k^3$) and gives an improvement for l>2.

http://publik.tuwien.ac.at/files/publik_255926.pdf