Fixed-parameter tractability results for feedback set problems in tournaments. (English) Zbl 1191.68349
Summary: Complementing recent progress on classical complexity and polynomial-time approximability of feedback set problems in (bipartite) tournaments, we extend and improve fixed-parameter tractability results for these problems. We show that Feedback Vertex Set in tournaments is amenable to the novel iterative compression technique, and we provide a depth-bounded search tree for Feedback Arc Set in bipartite tournaments based on a new forbidden subgraph characterization. Moreover, we apply the iterative compression technique to \(d\)-Hitting Set, which generalizes Feedback Vertex Set in tournaments, and obtain improved upper bounds for the time needed to solve 4-Hitting Set and 5-Hitting Set. Using our parameterized algorithm for Feedback Vertex Set in tournaments, we also give an exact (not parameterized) algorithm for it running in \(O(1.709^n)\) time, where \(n\) is the number of input graph vertices, answering a question of G. J. Woeginger [Discrete Appl. Math. 156, No. 3, 397–405 (2008; Zbl 1165.90613)].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C27 | Combinatorial optimization |
| 90C60 | Abstract computational complexity for mathematical programming problems |
Keywords:
feedback arc set; feedback vertex set; tournament; bipartite tournament; fixed-parameter tractability; iterative compressionCitations:
Zbl 1165.90613References:
| [1] | Abu-Khzam, F. N., Kernelization algorithms for \(d\)-hitting set problems, (Proceedings of the 10th Workshop on Algorithms and Data Structures. Proceedings of the 10th Workshop on Algorithms and Data Structures, WADS ’07. Proceedings of the 10th Workshop on Algorithms and Data Structures. Proceedings of the 10th Workshop on Algorithms and Data Structures, WADS ’07, LNCS, vol. 4619 (2007), Springer), 434-445 · Zbl 1209.68610 |
| [2] | Abu-Khzam, F. N.; Fernau, H., Kernels: Annotated, proper and induced, (Proceedings of the 2nd International Workshop on Parameterized and Exact Computation. Proceedings of the 2nd International Workshop on Parameterized and Exact Computation, IWPEC ’06. Proceedings of the 2nd International Workshop on Parameterized and Exact Computation. Proceedings of the 2nd International Workshop on Parameterized and Exact Computation, IWPEC ’06, LNCS, vol. 4169 (2006), Springer), 264-275 · Zbl 1154.68559 |
| [3] | Abu-Khzam, F. N.; Collins, R. L.; Fellows, M. R.; Langston, M. A.; Suters, W. H.; Symons, C. T., Kernelization algorithms for the vertex cover problem: Theory and experiments, (Proceedings of the 6th Workshop on Algorithm Engineering and Experiments. Proceedings of the 6th Workshop on Algorithm Engineering and Experiments, ALENEX ’04 (2004), SIAM), 62-69 |
| [4] | Ailon, N.; Charikar, M.; Newman, A., Aggregating inconsistent information: Ranking and clustering, J. ACM, 55, 5, 23 (2008) · Zbl 1325.68102 |
| [5] | Alon, N., Ranking tournaments, SIAM J. Discrete Math., 20, 1, 137-142 (2006) · Zbl 1112.05043 |
| [6] | Alon, N.; Lokshtanov, D.; Saurabh, S., Fast FAST, (Proceedings of the 36th International Colloquium on Automata, Languages and Programming. Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP ’09. Proceedings of the 36th International Colloquium on Automata, Languages and Programming. Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP ’09, LNCS, vol. 5555 (2009), Springer), 49-58 · Zbl 1248.68547 |
| [7] | Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2002), Springer · Zbl 1001.05002 |
| [8] | Cai, M.-C.; Deng, X.; Zang, W., An approximation algorithm for feedback vertex sets in tournaments, SIAM J. Comput., 30, 6, 1993-2007 (2001) · Zbl 0980.68053 |
| [9] | Cai, M.-C.; Deng, X.; Zang, W., A min-max theorem on feedback vertex sets, Math. Oper. Res., 27, 2, 361-371 (2002) · Zbl 1082.90583 |
| [10] | Chang, M.-S.; Wang, F.-H., Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs, Inform. Process. Lett., 43, 6, 293-295 (1992) · Zbl 0768.68126 |
| [11] | Charbit, P.; Thomassé, S.; Yeo, A., The minimum feedback arc set problem is NP-hard for tournaments, Combin. Probab. Comput., 16, 1-4 (2007) · Zbl 1120.05038 |
| [12] | Charon, I.; Hudry, O., A survey on the linear ordering problem for weighted or unweighted tournaments, 4OR: Quart. J. Oper. Res., 5, 1, 5-60 (2007) · Zbl 1126.05052 |
| [13] | Chen, J.; Kanj, I. A.; Xia, G., Improved parameterized upper bounds for vertex cover, (Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, MFCS ’06. Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, MFCS ’06, LNCS, vol. 4162 (2006), Springer), 238-249 · Zbl 1132.68421 |
| [14] | Chen, J.; Fomin, F. V.; Liu, Y.; Lu, S.; Villanger, Y., Improved algorithms for feedback vertex set problems, J. Comput. System Sci., 74, 7, 1188-1198 (2008) · Zbl 1152.68055 |
| [15] | Chen, J.; Liu, Y.; Lu, S.; O’Sullivan, B.; Razgon, I., A fixed-parameter algorithm for the directed feedback vertex set problem, J. ACM, 55, 5, 21 (2008) · Zbl 1325.68104 |
| [16] | Conitzer, V., Computing Slater rankings using similarities among candidates, (Proceedings of the 21st National Conference on Artificial Intelligence. Proceedings of the 21st National Conference on Artificial Intelligence, AAAI ’06 (2006), AAAI Press), 613-619 |
| [17] | Dehne, F. K.H. A.; Fellows, M. R.; Langston, M. A.; Rosamond, F. A.; Stevens, K., An \(O(2^{O(k)} n^3)\) FPT algorithm for the undirected feedback vertex set problem, Theory Comput. Syst., 41, 3, 479-492 (2007) · Zbl 1148.68037 |
| [18] | Dinur, I.; Safra, S., On the hardness of approximating minimum vertex-cover, Ann. of Math., 162, 1, 439-486 (2005) · Zbl 1084.68051 |
| [19] | Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer · Zbl 0914.68076 |
| [20] | Felner, A.; Korf, R. E.; Hanan, S., Additive pattern database heuristics, J. Artificial Intelligence Res., 21, 1-39 (2004) · Zbl 1080.68662 |
| [21] | H. Fernau, A top-down approach to search-trees: Improved algorithmics for 3-hitting set, Technical Report TR04-073, Electronic Colloquium on Computational Complexity, 2004, Algorithmica, in press; H. Fernau, A top-down approach to search-trees: Improved algorithmics for 3-hitting set, Technical Report TR04-073, Electronic Colloquium on Computational Complexity, 2004, Algorithmica, in press · Zbl 1184.68598 |
| [22] | H. Fernau, Parameterized Algorithmics: A graph-theoretic approach, Habilitationsschrift, Universität Tübingen, 2005; H. Fernau, Parameterized Algorithmics: A graph-theoretic approach, Habilitationsschrift, Universität Tübingen, 2005 |
| [23] | Festa, P.; Pardalos, P. M.; Resende, M. G.C., Feedback set problems, (Du, D. Z.; Pardalos, P. M., Handbook of Combinatorial Optimization, vol. A (1999), Kluwer), 209-258 · Zbl 1253.90193 |
| [24] | Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer · Zbl 1143.68016 |
| [25] | Fomin, F.; Gaspers, S.; Kratsch, D.; Liedloff, M.; Saurabh, S., Iterative compression and exact algorithms, (Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS ’08. Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS ’08, LNCS, vol. 5162 (2008), Springer), 335-346 · Zbl 1173.68537 |
| [26] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman · Zbl 0411.68039 |
| [27] | Guo, J.; Niedermeier, R., Invitation to data reduction and problem kernelization, ACM SIGACT News, 38, 1, 31-45 (2007) |
| [28] | Guo, J.; Gramm, J.; Hüffner, F.; Niedermeier, R.; Wernicke, S., Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, J. Comput. Syst. Sci., 72, 8, 1386-1396 (2006) · Zbl 1119.68134 |
| [29] | Guo, J.; Hüffner, F.; Moser, H., Feedback arc set in bipartite tournaments is NP-complete, Inform. Process. Lett., 102, 2-3, 62-65 (2007) · Zbl 1184.68264 |
| [30] | Guo, J.; Moser, H.; Niedermeier, R., Iterative compression for exactly solving NP-hard minimization problems, (Algorithmics of Large and Complex Networks. Algorithmics of Large and Complex Networks, LNCS, vol. 5515 (2009), Springer), 65-80 · Zbl 1248.68380 |
| [31] | Gupta, S., Feedback arc set problem in bipartite tournaments, Inform. Process. Lett., 105, 5, 150-154 (2008) · Zbl 1184.68636 |
| [32] | Gutin, G.; Yeo, A., Some parameterized problems on digraphs, Comput. J., 51, 3, 363-371 (2008) |
| [33] | F. Hüffner, Algorithms and experiments for parameterized approaches to hard graph problems, PhD thesis, Institut für Informatik, Friedrich-Schiller Universität Jena, 2007; F. Hüffner, Algorithms and experiments for parameterized approaches to hard graph problems, PhD thesis, Institut für Informatik, Friedrich-Schiller Universität Jena, 2007 · Zbl 1250.05107 |
| [34] | Hüffner, F.; Komusiewicz, C.; Moser, H.; Niedermeier, R., Fixed-parameter algorithms for cluster vertex deletion, (Proceedings of the 8th Latin American Theoretical Informatics Symposium. Proceedings of the 8th Latin American Theoretical Informatics Symposium, LATIN ’08. Proceedings of the 8th Latin American Theoretical Informatics Symposium. Proceedings of the 8th Latin American Theoretical Informatics Symposium, LATIN ’08, LNCS, vol. 4598 (2008), Springer), 711-722, Theory Comput. Syst., in press · Zbl 1136.68465 |
| [35] | Hunt, J. W.; Szymanski, T. G., A fast algorithm for computing longest common subsequences, Commun. ACM, 20, 5, 350-353 (1977) · Zbl 0354.68078 |
| [36] | Kenyon-Mathieu, C.; Schudy, W., How to rank with few errors: A PTAS for weighted feedback arc set on tournaments, (Proceedings of the 39th ACM Symposium on Theory of Computing. Proceedings of the 39th ACM Symposium on Theory of Computing, STOC ’07 (2007), ACM), 95-103 · Zbl 1232.68181 |
| [37] | Khot, S.; Regev, O., Vertex cover might be hard to approximate to within \(2 - \&z.epsi;\), J. Comput. System Sci., 74, 3, 335-349 (2008) · Zbl 1133.68061 |
| [38] | Knuth, D. E., The Art of Computer Programming, vol. 4 (2004), Addison-Wesley |
| [39] | Moon, J. W., On maximal transitive subtournaments, Proc. Edinb. Math. Soc., 17, 345-349 (1971) · Zbl 0234.05108 |
| [40] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038 |
| [41] | Niedermeier, R.; Rossmanith, P., An efficient fixed parameter algorithm for 3-Hitting Set, J. Discrete Algorithms, 1, 1, 89-102 (2003) · Zbl 1118.68511 |
| [42] | 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 |
| [43] | Raman, V.; Saurabh, S.; Sikdar, S., Efficient exact algorithms through enumerating maximal independent sets and other techniques, Theory Comput. Syst., 41, 3, 563-587 (2007) · Zbl 1148.68054 |
| [44] | Sasatte, P., Improved FPT algorithm for feedback vertex set problem in bipartite tournament, Inform. Process. Lett., 105, 3, 79-82 (2007) · Zbl 1184.68611 |
| [45] | Sasatte, P., Improved approximation algorithm for the feedback set problem in a bipartite tournament, Oper. Res. Lett., 36, 5, 602-604 (2008) · Zbl 1210.90168 |
| [46] | Schwikowski, B.; Speckenmeyer, E., On enumerating all minimal solutions of feedback problems, Discrete Appl. Math., 117, 1-3, 253-265 (2002) · Zbl 1004.68122 |
| [47] | Speckenmeyer, E., On feedback problems in digraphs, (Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science, WG ’89. Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science, WG ’89, LNCS, vol. 411 (1989), Springer), 218-231 · Zbl 0768.68181 |
| [48] | M. Wahlström, Algorithms, measures and upper bounds for satisfiability and related problems, PhD thesis, Department of Computer and Information Science, Linköpings universitet, Sweden, 2007; M. Wahlström, Algorithms, measures and upper bounds for satisfiability and related problems, PhD thesis, Department of Computer and Information Science, Linköpings universitet, Sweden, 2007 |
| [49] | Woeginger, G. J., Open problems around exact algorithms, Discrete Appl. Math., 156, 3, 397-405 (2008) · Zbl 1165.90613 |
| [50] | van Zuylen, A., Linear programming based approximation algorithms for feedback set problems in bipartite tournaments, (Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation. Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation, TAMC ’09. Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation. Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation, TAMC ’09, LNCS, vol. 5532 (2009), Springer), 370-379 · Zbl 1241.68133 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
