Skip to main content
SpringerLink
Log in

A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

The k-feedback arc set problem is to determine whether there is a set F of at most k arcs in a directed graph G such that the removal of F makes G acyclic. The k-feedback arc set problems in tournaments and bipartite tournaments (k-FAST and k-FASBT) have applications in ranking aggregation and have been extensively studied from the viewpoint of parameterized complexity. By introducing a new concept called “bimodule”, we provide a problem kernel with O(k 2) vertices for k-FASBT, which improves the previous result by a factor of k.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Abu-Khzam, F.N.: A kernelization algorithm for d-hitting set. J. Comput. Syst. Sci. 76(7), 524–531 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  2. Alon, N.: Ranking tournaments. SIAM J. Discrete Math. 20(1), 137–142 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  3. Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: Albers, S., et al. (eds.) ICALP 2009. Lecture Notes in Computer Science, vol. 5555, pp. 49–58. Springer, Heidelberg (2009)

    Google Scholar 

  4. Cai, M., Deng, M., Zang, W.: A min-max theorem on feedback vertex sets. Math. Oper. Res. 27(2), 361–371 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  5. Bessy, S., Fomin, F.V., Gaspers, S., Paul, C., Perez, A., Saurabh, S., Thomassé, S.: Kernels for feedback arc set in tournaments. J. Comput. Syst. Sci. 77(6), 1071–1078 (2011)

    Article  MATH  Google Scholar 

  6. Charbit, P., Thomassé, S., Yeo, A.: The minimum feedback arc set problem is NP-hard for tournaments. Comb. Probab. Comput. 16(1), 1–4 (2007)

    Article  MATH  Google Scholar 

  7. Dom, M., Guo, J., Hüffner, F., Niedermeier, R., Truß, A.: Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms 8(1), 76–86 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  8. Guo, J., Hüffner, F., Moser, H.: Feedback arc set in bipartite tournaments is NP-complete. Inf. Process. Lett. 102(2–3), 62–65 (2007)

    Article  MATH  Google Scholar 

  9. Hsiao, S.: Fixed-parameter complexity of feedback vertex set in bipartite tournaments. In: Asano, T., et al. (eds.) ISAAC 2011. Lecture Notes in Computer Science, vol. 7074, pp. 344–353. Springer, Heidelberg (2011)

    Google Scholar 

  10. Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set in tournament, Kemeny rank aggregation and betweenness tournament. In: Cheong, O., Chwa, K., Park, K. (eds.) ISAAC 2010. Lecture Notes in Computer Science, vol. 6506, pp. 3–14. Springer, Heidelberg (2010)

    Google Scholar 

  11. Kemeny, J.: Mathematics without numbers. Daedalus 88(4), 571–591 (1959)

    Google Scholar 

  12. Misra, P., Raman, V., Ramanujan, M.S., Saurabh, S.: A polynomial kernel for feedback arc set on bipartite tournaments. In: Asano, T., et al. (eds.) ISAAC 2011. Lecture Notes in Computer Science, vol. 7074, pp. 333–343. Springer, Heidelberg (2011)

    Google Scholar 

  13. Paul, C., Perez, A., Thomassé, S.: Conflict packing yields linear vertex-kernels for k-FAST, k-dense RTI and a related problem. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. Lecture Notes in Computer Science, vol. 6907, pp. 497–507. Springer, Heidelberg (2011)

    Google Scholar 

  14. Sanghvi, B., Koul, N., Honavar, V.: Identifying and eliminating inconsistencies in mappings across hierarchical ontologies. In: Meersman, R., Dillon, T., Herrero, P. (eds.) OTM 2010. Lecture Notes in Computer Science, vol. 6427, pp. 999–1008. Springer, Heidelberg (2010)

    Google Scholar 

  15. Speckenmeyer, E.: On feedback problems in digraphs. In: Nagl, M. (ed.) WG 1989. Lecture Notes in Computer Science, vol. 411, pp. 218–231. Springer, Heidelberg (1990)

    Google Scholar 

  16. Sasatte, P.: Improved FPT algorithm for feedback vertex set problem in bipartite tournament. Inf. Process. Lett. 105(3), 79–82 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  17. Wahlström, M.: Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. Thesis, Linköpings Universitet (2007)

  18. Raman, V., Saurabh, S.: Parameterized algorithms for feedback set problems and their duals in tournaments. Theor. Comput. Sci. 351(3), 446–458 (2006)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors thank all the anonymous reviewers for their comments to improve the presentation of the paper.

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China

    Mingyu Xiao

  2. Universität des Saarlandes, Campus E 1.7, 66123, Saarbrücken, Germany

    Jiong Guo

Authors
  1. Mingyu Xiao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jiong Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mingyu Xiao.

Additional information

M. Xiao supported by National Natural Science Foundation of China under the Grant 60903007 and Fundamental Research Funds for the Central Universities under the Grant ZYGX2012J069.

J. Guo supported by the DFG Excellence Cluster MMCI.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Xiao, M., Guo, J. A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments. Algorithmica 71, 87–97 (2015). https://doi.org/10.1007/s00453-013-9783-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-013-9783-2

Keywords

Search

Navigation