Abstract
In the k -Feedback Arc/Vertex Set problem we are given a directed graph D and a positive integer k and the objective is to check whether it is possible to delete at most k arcs/vertices from D to make it acyclic. Dom et al.[CIAC, 2006] initiated a study of the Feedback Arc Set problem on bipartite tournaments (k -FASBT) in the realm of parameterized complexity. They showed that k -FASBT can be solved in time O(3.373k n 6) on bipartite tournaments having n vertices. However, until now there was no known polynomial sized problem kernel for k -FASBT. In this paper we obtain a cubic vertex kernel for k -FASBT. This completes the kernelization picture for the Feedback Arc/Vertex Set problem on tournaments and bipartite tournaments, as for all other problems polynomial kernels were known before. We obtain our kernel using a non-trivial application of “independent modules” which could be of independent interest.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abu-Khzam, F.N.: A kernelization algorithm for d-hitting set. Journal of Computer and System Sciences 76(7), 524–531 (2010)
Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. In: ACM Symposium on Theory of Computing (STOC), pp. 684–693 (2005)
Alon, N.: Ranking tournaments. SIAM J. Discrete Math. 20(1), 137–142 (2006)
Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 49–58. Springer, Heidelberg (2009)
Bang-Jensen, J., Thomassen, C.: A polynomial algorithm for the 2-path problem for semicomplete digraphs. SIAM J. Discrete Math. 5(3), 366–376 (1992)
Bessy, S., Fomin, F.V., Gaspers, S., Paul, C., Perez, A., Saurabh, S., Thomassé, S.: Kernels for feedback arc set in tournaments. In: FSTTCS, pp. 37–47 (2009)
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009)
Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. In: FOCS, pp. 629–638 (2009)
Borda, J.: Mémoire sur les élections au scrutin. Histoire de l’Académie Royale des Sciences (1781)
Cheng Cai, M., Deng, X., Zang, W.: A min-max theorem on feedback vertex sets. Math. Oper. Res. 27(2), 361–371 (2002)
Charbit, P., Thomassé, S., Yeo, A.: The minimum feedback arc set problem is NP-hard for tournaments. Combin. Probab. Comput. 16(1), 1–4 (2007)
Cohen, W.W., Schapire, R.E., Singer, Y.: Learning to order things. In: Advances in Neural Information Processing Systems (NIPS), pp. 451–457 (1997)
Condorcet, M.: Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix (1785)
Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: STOC, pp. 251–260. ACM (2010)
Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through Colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 378–389. Springer, Heidelberg (2009)
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)
Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: World Wide Web Conference, WWW (2001)
Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: SODA, pp. 503–510 (2010)
Guo, J.: A more effective linear kernelization for cluster editing. Theor. Comput. Sci. 410(8-10), 718–726 (2009)
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)
Gupta, S.: Feedback arc set problem in bipartite tournaments. Inf. Process. Lett. 105(4), 150–154 (2008)
Habib, M., Paul, C.: A survey of the algorithmic aspects of modular decomposition. Computer Science Review 4(1), 41–59 (2010)
Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set tournament, kemeny rank aggregation and betweenness tournament. CoRR abs/1006.4396 (2010)
Kemeny, J.: Mathematics without numbers. Daedalus 88, 571–591 (1959)
Kemeny, J., Snell, J.: Mathematical models in the social sciences. Blaisdell (1962)
Kenyon-Mathieu, C., Schudy, W.: How to rank with few errors. In: ACM Symposium on Theory of Computing (STOC), pp. 95–103 (2007)
Raman, V., Saurabh, S.: Parameterized algorithms for feedback set problems and their duals in tournaments. Theor. Comput. Sci. 351(3), 446–458 (2006)
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. LNCS, vol. 6427, pp. 999–1008. Springer, Heidelberg (2010)
Speckenmeyer, E.: On Feedback Problems in Digraphs. In: Nagl, M. (ed.) WG 1989. LNCS, vol. 411, pp. 218–231. Springer, Heidelberg (1990)
Tedder, M., Corneil, D.G., Habib, M., Paul, C.: Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 634–645. Springer, Heidelberg (2008)
Thomassé, S.: A 4k 2 kernel for feedback vertex set. ACM Transactions on Algorithms 6(2) (2010)
van Zuylen, A., Hegde, R., Jain, K., Williamson, D.P.: Deterministic pivoting algorithms for constrained ranking and clustering problems. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 405–414 (2007)
van Zuylen, A.: Linear programming based approximation algorithms for feedback set problems in bipartite tournaments. Theor. Comput. Sci. 412(23), 2556–2561 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Misra, P., Raman, V., Ramanujan, M.S., Saurabh, S. (2011). A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments. In: Asano, T., Nakano, Si., Okamoto, Y., Watanabe, O. (eds) Algorithms and Computation. ISAAC 2011. Lecture Notes in Computer Science, vol 7074. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25591-5_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-25591-5_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25590-8
Online ISBN: 978-3-642-25591-5
eBook Packages: Computer ScienceComputer Science (R0)