Talks and Poster Presentations (with Proceedings-Entry):
M. S. Ramanujan:
"A Faster Parameterized Algorithm for Group Feedback Edge Set";
Talk: International Workshop on Graph-Theoretic Concepts in Computer Science (WG),
Istanbul, Türkei;
2016-06-22
- 2016-06-24; in: "Graph-Theoretic Concepts in Computer Science",
(2016),
ISBN: 978-3-662-53535-6;
269
- 281.
English abstract:
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.
Electronic version of the publication:
http://publik.tuwien.ac.at/files/publik_255926.pdf
Created from the Publication Database of the Vienna University of Technology.