×

zbMATH — the first resource for mathematics

Kernels for feedback arc set in tournaments. (English) Zbl 1235.05134
From the abstract: “A tournament \(T=(V,A)\) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter \(k\), the Feedback Arc Set problem asks whether the given digraph has a set of \(k\) arcs whose removal results in an acyclic digraph. The Feedback Arc Set problem restricted to tournaments is known as the \(k\)-Feedback Arc Set in Tournaments (\(k\)-FAST) problem. In this paper we obtain a linear vertex kernel for \(k\)-FAST. That is, we give a polynomial time algorithm which given an input instance T to \(k\)-FAST obtains an equivalent instance \(T^{{\prime}}\) on \(O(k)\) vertices. In fact, given any fixed \(\epsilon >0\), the kernelized instance has at most \((2+\epsilon)k\) vertices. Our result improves the previous known bound of \(O(k^{2})\) on the kernel size for \(k\)-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for \(k\)-FAST.”

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abu-Khzam, F.N., A kernelization algorithm for d-hitting set, J. comput. system sci., 76, 7, 524-531, (2010) · Zbl 1197.68083
[2] N. Ailon, M. Charikar, A. Newman, Aggregating inconsistent information: ranking and clustering, in: ACM Symposium on Theory of Computing (STOC), 2005, pp. 684-693. · Zbl 1192.90252
[3] Alon, N., Ranking tournaments, SIAM J. discrete math., 20, 1, 137-142, (2006) · Zbl 1112.05043
[4] Alon, N.; Lokshtanov, D.; Saurabh, S., Fast FAST, (), 49-58 · Zbl 1248.68547
[5] Bartholdi, J.; Tovey, C.A.; Trick, M.A., Voting schemes for which it can be difficult to tell who won the election, Soc. choice welf., 6, 2, 157-165, (1989) · Zbl 0672.90004
[6] Bodlaender, H.L.; Downey, R.G.; Fellows, M.R.; Hermelin, D., On problems without polynomial kernels, J. comput. system sci., 75, 8, 423-434, (2009) · Zbl 1192.68288
[7] H.L. Bodlaender, F.V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, D.M. Thilikos, (Meta) Kernelization, in: FOCS, 2009, pp. 629-638. · Zbl 1292.68089
[8] J. Borda, Mémoire sur les élections au scrutin, Histoire de lʼAcadémie Royale des Sciences, 1781.
[9] N. Bousquet, J. Daligault, S. Thomassé, A. Yeo, A polynomial kernel for multicut in trees, in: Symposium on Theoretical Aspects of Computer Science (STACS), 2009, pp. 183-194. · Zbl 1236.68104
[10] 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) · Zbl 1120.05038
[11] Charon, I.; Hudry, O., A survey on the linear ordering problem for weighted or unweighted tournaments, 4or, 5, 1, 5-60, (2007) · Zbl 1126.05052
[12] W.W. Cohen, R.E. Schapire, Y. Singer, Learning to order things, in: Advances in Neural Information Processing Systems (NIPS), 1997, pp. 451-457. · Zbl 0915.68031
[13] M. Condorcet, Essai sur lʼapplication de lʼanalyse à la probabilité des décisions rendues à la pluralité des voix, 1785.
[14] D. Coppersmith, L. Fleischer, A. Rudra, Ordering by weighted number of wins gives a good ranking for weighted tournaments, in: ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006, pp. 776-782. · Zbl 1192.05060
[15] Dell, H.; van Melkebeek, D., Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses, (), 251-260 · Zbl 1293.68132
[16] Dom, M.; Guo, J.; Hüffner, F.; Niedermeier, R.; Truß, A., Fixed-parameter tractability results for feedback set problems in tournaments, (), 320-331 · Zbl 1183.68419
[17] Dom, M.; Lokshtanov, D.; Saurabh, S., Incompressibility through colors and ids, (), 378-389 · Zbl 1248.68243
[18] C. Dwork, R. Kumar, M. Naor, D. Sivakumar, Rank aggregation revisited, Technical report.
[19] C. Dwork, R. Kumar, M. Naor, D. Sivakumar, Rank aggregation methods for the web, in: World Wide Web Conference (WWW), 2001.
[20] Erdös, P.; Moon, J.W., On sets on consistent arcs in tournaments, Canad. math. bull., 8, 269-271, (1965) · Zbl 0137.43301
[21] F.V. Fomin, D. Lokshtanov, V. Raman, S. Saurabh, Fast local search algorithm for weighted feedback arc set in tournaments, in: AAAI, 2010, pp. 65-70.
[22] H.A. Jung, On subgraphs without cycles in tournaments, Combinatorial Theory and Its Applications II, 1970, pp. 675-677.
[23] Karpinski, M.; Schudy, W., Faster algorithms for feedback arc set tournament, kemeny rank aggregation and betweenness tournament, corr, (2010) · Zbl 1310.68272
[24] Kemeny, J., Mathematics without numbers, Daedalus, 88, 571-591, (1959)
[25] Kemeny, J.; Snell, J., Mathematical models in the social sciences, (1962), Blaisdell · Zbl 0256.92003
[26] C. Kenyon-Mathieu, W. Schudy, How to rank with few errors, in: ACM Symposium on Theory of Computing (STOC), 2007, pp. 95-103. · Zbl 1232.68181
[27] McConnell, R.M.; de Montgolfier, F., Linear-time modular decomposition of directed graphs, Discrete appl. math., 145, 2, 198-209, (2005) · Zbl 1055.05123
[28] Raman, V.; Saurabh, S., Parameterized algorithms for feedback set problems and their duals in tournaments, Theoret. comput. sci., 351, 3, 446-458, (2006) · Zbl 1086.68105
[29] Reid, K.D.; Parker, E.T., Disproof of a conjecture of Erdös and Moser on tournaments, J. combin. theory, 9, 225-238, (1970) · Zbl 0204.24605
[30] Seshu, S.; Reed, M.B., Linear graphs and electrical networks, (1961), Addison-Wesley · Zbl 0102.34001
[31] Slater, P., Inconsistencies in a schedule of paired comparisons, Biometrika, 48, 303-312, (1961)
[32] Speckenmeyer, E., On feedback problems in digraphs, (), 218-231 · Zbl 0768.68181
[33] Spencer, J., Optimal ranking of tournaments, Networks, 1, 135-138, (1971) · Zbl 0236.05110
[34] Thomassé, S., A \(4 k^2\) kernel for feedback vertex set, ACM trans. algorithms, 6, 2, (2010)
[35] A. van Zuylen, Deterministic approximation algorithms for ranking and clusterings, Technical Report 1431, Cornell ORIE, 2005.
[36] A. van Zuylen, R. Hegde, K. Jain, D.P. Williamson, Deterministic pivoting algorithms for constrained ranking and clustering problems, in: ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, pp. 405-414. · Zbl 1302.68326
[37] Younger, D.H., Minimum feedback arc sets for a directed graph, IEEE trans. circuit theory, 10, 238-245, (1963)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.