A Faster Parameterized Algorithm for n class="a-plus-plus emphasis type-small-caps">Group Feedback Edge Setn>

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9941
• 期：1
• 页码：269-281
• 全文大小：290 KB
• 参考文献：1.Chen, J., Liu, Y., Lu, S.: An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica 55(1), 1–13 (2009)MathSciNet CrossRef MATH
  2.Chitnis, R.H., Cygan, M., Hajiaghayi, M., Pilipczuk, M., Pilipczuk, M.: Designing FPT algorithms for cut problems using randomized contractions. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, 20–23 October 2012, pp. 460–469 (2012)
  3.Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Switzerland (2015)CrossRef MATH
  4.Cygan, M., Pilipczuk, M., Pilipczuk, M.: On group feedback vertex set parameterized by the size of the cutset. Algorithmica 74(2), 630–642 (2016)MathSciNet CrossRef MATH
  5.Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. TOCT 5(1), 3 (2013)MathSciNet CrossRef MATH
  6.Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864–894 (1994)MathSciNet CrossRef MATH
  7.Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)CrossRef MATH
  8.Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)MATH
  9.Geelen, J., Gerards, B.: Excluding a group-labelled graph. J. Comb. Theory Ser. B 99(1), 247–253 (2009)MathSciNet CrossRef MATH
  10.Guillemot, S.: FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optim. 8(1), 61–71 (2011)MathSciNet CrossRef MATH
  11.Harary, F.: On the notion of balance of a signed graph. Michigan Math. J. 2(2), 143–146 (1953)MathSciNet CrossRef MATH
  12.Iwata, Y., Oka, K., Yoshida, Y.: Linear-time FPT algorithms via network flow. In: SODA, pp. 1749–1761 (2014)
  13.Iwata, Y., Wahlström, M., Yoshida, Y.: Half-integrality, lp
  anching and FPT algorithms (2013). CoRR, abs/1310.2841
  14.Kawarabayashi, K., Wollan, P.: Non-zero disjoint cycles in highly connected group labelled graphs. J. Comb. Theory, Ser. B 96(2), 296–301 (2006)MathSciNet CrossRef MATH
  15.Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. ACM Trans. Algorithms 11(2), 15:1–15:31 (2014)MathSciNet CrossRef
  16.Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394–406 (2006)MathSciNet CrossRef MATH
  17.Nemhauser, G.L., Trotter Jr., L.E.: Properties of vertex packing and independence system polyhedra. Math. Program. 6, 48–61 (1974)MathSciNet CrossRef MATH
  18.Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford (2006)CrossRef MATH
  19.Ramanujan, M.S., Saurabh, S.: Linear time parameterized algorithms via skew-symmetric multicuts. In: SODA, pp. 1739–1748 (2014)
  20.Wahlström, M.: Half-integrality, lp
  anching and FPT algorithms. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, 5–7 January 2014, pp. 1762–1781 (2014)
  21.Wollan, P.: Packing cycles with modularity constraints. Combinatorica 31(1), 95–126 (2011)MathSciNet CrossRef MATH
  
• 作者单位：M. S. Ramanujan (14)
  
  14. Vienna University of Technology, Vienna, Austria
  
• 丛书名：Graph-Theoretic Concepts in Computer Science
• ISBN：978-3-662-53536-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9941

文摘

In the Group Feedback Edge Set (\(\ell \)) (Group FES(\(\ell \))) problem, the input is a group-labeled graph G over a group \(\varGamma \) of order \(\ell \) 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 Group FES(\(\ell \)) was motivated by the fact that it generalizes the classical Edge Bipartization problem when \(\ell =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 \({\mathcal {O}}(4^kn^{{\mathcal {O}}(1)})\) (even in the oracle access model) and \({\mathcal {O}}(\ell ^{2k}m)\) respectively. In this paper, we give an algorithm for Group FES(\(\ell \)) running in time \({\mathcal {O}}(4^kk^{3}\ell (m+n))\). Our algorithm matches that of Iwata et al. when \(\ell =2\) (upto a multiplicative factor of \(k^3\)) and gives an improvement for \(\ell >2\).