Document Open Access Logo

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments

Authors Mithilesh Kumar, Daniel Lokshtanov

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.24.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Mithilesh Kumar
Daniel Lokshtanov

Cite As Get BibTex

Mithilesh Kumar and Daniel Lokshtanov. Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.24

Abstract

A bipartite tournament is a directed graph T:=(A cup B, E) such that every pair of vertices (a,b), a in A, b in B are connected by an arc, and no arc connects two vertices of A or two vertices of B. A  feedback vertex set is a set S of vertices in T such that T - S is acyclic. In this article we consider the Feedback Vertex Set problem in bipartite tournaments. Here the input is a bipartite tournament T on n vertices together with an integer k, and the task is to determine whether T has a feedback vertex set of size at most k. We give a new algorithm for Feedback Vertex Set in Bipartite Tournaments. The running time of our algorithm is upper-bounded by O(1.6181^k + n^{O(1)}), improving over the previously best known algorithm with running time (2^k)k^{O(1)} + n^{O(1)} [Hsiao, ISAAC 2011]. As a by-product, we also obtain the fastest currently known exact exponential-time algorithm for the problem, with running time O(1.3820^n).

Subject Classification

Keywords
  • Parameterized algorithms
  • Exact algorithms
  • Feedback vertex set
  • Tour- naments
  • Bipartite tournaments

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567-583, 1986. URL: http://dx.doi.org/10.1016/0196-6774(86)90019-2.
  2. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math., 12(3):289-297, 1999. Google Scholar
  3. Lowell W. Beineke and Charles H. C. Little. Cycles in bipartite tournaments. Journal of Combinatorial Theory, Series B, 32(2):140-145, 1982. Google Scholar
  4. Mao-cheng Cai, Xiaotie Deng, and Wenan Zang. An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput., 30(6):1993-2007, 2000. Google Scholar
  5. Mao-cheng Cai, Xiaotie Deng, and Wenan Zang. A min-max theorem on feedback vertex sets. Math. Oper. Res., 27(2):361-371, 2002. URL: http://dx.doi.org/10.1287/moor.27.2.361.328.
  6. Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, and Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55(5), 2008. URL: http://dx.doi.org/10.1145/1411509.1411511.
  7. C. R. J. Clapham. The bipartite tournament associated with a fabric. Discrete Mathematics, 57(1):195-197, 1985. Google Scholar
  8. Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld. Approximating connectivity domination in weighted bounded-genus graphs. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 584-597, 2016. Google Scholar
  9. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 150-159, 2011. Google Scholar
  10. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866-893, 2005. Google Scholar
  11. Erik D. Demaine and Mohammad Taghi Hajiaghayi. Bidimensionality: new connections between FPT algorithms and ptass. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 590-601, 2005. Google Scholar
  12. Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, and Anke Truß. Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms, 8(1):76-86, 2010. Google Scholar
  13. P. Erdős and L. Pósa. On independent circuits contained in a graph. Canad. J. Math, 17:347-352, 1965. Google Scholar
  14. Guy Even, Joseph Naor, Baruch Schieber, and Madhu Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151-174, 1998. Google Scholar
  15. Paola Festa, Panos M. Pardalos, and Mauricio G. C. Resende. Feedback set problems. In Handbook of combinatorial optimization, pages 209-258. Springer, 1999. Google Scholar
  16. Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh. Exact algorithms via monotone local search. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 764-775, 2016. URL: http://dx.doi.org/10.1145/2897518.2897551.
  17. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Bidimensionality and EPTAS. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 748-759, 2011. Google Scholar
  18. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 503-510, 2010. Google Scholar
  19. Fedor V. Fomin and Yngve Villanger. Finding induced subgraphs via minimal triangulations. In 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France, pages 383-394, 2010. Google Scholar
  20. Leo Moser Frank Harary. The theory of round robin tournaments. The American Mathematical Monthly, 73(3):231-246, 1966. URL: http://www.jstor.org/stable/2315334.
  21. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman and Co., 1979. Google Scholar
  22. Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar. Beating the random ordering is hard: Every ordering CSP is approximation resistant. SIAM J. Comput., 40(3):878-914, 2011. Google Scholar
  23. Gregory Gutin and Anders Yeo. Some parameterized problems on digraphs. Comput. J., 51(3):363-371, 2008. Google Scholar
  24. Sheng-Ying Hsiao. Fixed-parameter complexity of feedback vertex set in bipartite tournaments. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings, pages 344-353, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25591-5_36.
  25. Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York., pages 85-103, 1972. Google Scholar
  26. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Inf. Process. Lett., 114(10):556-560, 2014. Google Scholar
  27. Mithilesh Kumar and Daniel Lokshtanov. Faster exact and parameterized algorithm for feedback vertex set in tournaments. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pages 49:1-49:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.49.
  28. Igor Razgon. Computing minimum directed feedback vertex set in o(1.9977^n). In Theoretical Computer Science, 10th Italian Conference, ICTCS 2007, Rome, Italy, October 3-5, 2007, Proceedings, pages 70-81, 2007. Google Scholar
  29. Bruce Reed, Neil Robertson, Paul Seymour, and Robin Thomas. Packing directed circuits. Combinatorica, 16(4):535-554, 1996. Google Scholar
  30. Prashant Sasatte. Improved FPT algorithm for feedback vertex set problem in bipartite tournament. Inf. Process. Lett., 105(3):79-82, 2008. URL: http://dx.doi.org/10.1016/j.ipl.2007.08.014.
  31. A. Truß. Parameterized algorithms for feedback set problems in tournaments. PhD thesis, Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2005. Google Scholar
  32. Shuichi Ueno, Yoji Kajitani, and Shin'ya Gotoh. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Mathematics, 72(1-3):355-360, 1988. Google Scholar
  33. Anke van Zuylen. Linear programming based approximation algorithms for feedback set problems in bipartite tournaments. Theor. Comput. Sci., 412(23):2556-2561, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2010.10.047.
  34. Mingyu Xiao and Hiroshi Nagamochi. An improved exact algorithm for undirected feedback vertex set. J. Comb. Optim., 30(2):214-241, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact