×

zbMATH — the first resource for mathematics

Feedback vertex sets in tournaments. (English) Zbl 1259.05070
Summary: We study combinatorial and algorithmic questions around minimal feedback vertex sets (FVS) in tournament graphs. On the combinatorial side, we derive upper and lower bounds on the maximum number of minimal FVSs in an \(n\)-vertex tournament.
We prove that every tournament on \(n\) vertices has at most \(1.6740^{n}\) minimal FVSs, and that there is an infinite family of tournaments, all having at least \(1.5448^{n}\) minimal FVSs. This improves and extends the bounds of J. W. Moon [Proc. Edinb. Math. Soc., II. Ser. 17, 345–349 (1971; Zbl 0234.05108)]. On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal FVSs of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum-sized FVS in a tournament.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
05C30 Enumeration in graph theory
68P05 Data structures
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Bang’Jensen, Digraphs: Theory, Algorithms and Applications (2002) · Zbl 1001.05002
[2] Banks, Sophisticated voting outcomes and agenda control, Soc Choice Welfare 1 (4) pp 295– (1985) · Zbl 0597.90011
[3] Björklund, Set partitioning via inclusion-exclusion, SIAM J Comput 39 (2) pp 546– (2009) · Zbl 1215.05056
[4] Brandt, Minimal stable sets in tournaments, J Econ Theory 146 (4) pp 1481– (2011) · Zbl 1247.91055
[5] Byskov, Enumerating maximal independent sets with applications to graph colouring, Oper Res Lett 32 (6) pp 547– (2004) · Zbl 1052.05055
[6] Byskov, On the number of maximal bipartite subgraphs of a graph, J Graph Theory 48 (2) pp 127– (2005) · Zbl 1059.05045
[7] Dom, Fixed-parametertractability results for feedback set problems in tournaments, J Discrete Algorithms 8 (1) pp 320– (2010)
[8] Eppstein, Small maximal independent sets and faster exact graph coloring, J Graph Algorithms Appl 7 (2) pp 131– (2003) · Zbl 1027.05092
[9] Fomin, Iterative compression and exact algorithms, Theor Comput Sci 411 (7-9) pp 1045– (2010) · Zbl 1186.68187
[10] Fomin, On the minimum feedback vertex set problem: exact and enumeration algorithms, Algorithmica 52 (2) pp 293– (2008) · Zbl 1170.68029
[11] Fomin, Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications, ACM Trans Algorithms 5 (1) pp 1– (2008) · Zbl 1445.05101
[12] Fomin, Treewidth computation and extremal combinatorics, in: In Proc. of ICALP 2008 pp 210– (2008) · Zbl 1152.05376
[13] Fomin, Finding induced subgraphs via minimal triangulations, in: Proceedings of STACS 2010 pp 383– (2010) · Zbl 1230.68108
[14] Gaspers, On independent sets and bicliques in graphs, in: Proceedings of WG 2008 pp 171– (2008) · Zbl 1202.05096
[15] Gaspers, Feedback vertex sets in tournaments, in: Proceedings of ESA 2010 pp 267– (2010) · Zbl 1287.05051
[16] Gupta, Fast exponential algorithms for maximum r-regularinduced subgraph problems, in: Proceedings of FSTTCS 2006 pp 139– (2006)
[17] Harary, The theory of round robin tournaments, Amer Math Monthly 73 (3) pp 231– (1966) · Zbl 0142.41602
[18] Landau, On dominance relations and the structure of animal societies. III: the condition for a score structure, Bull Math Biophys 15 pp 143– (1953)
[19] Lawler, A note on the complexity of the chromatic number problem, Inform Process Lett 5 (3) pp 66– (1976) · Zbl 0336.68021
[20] R. E. Miller D. E. Muller A problem of maximum consistent subsets IBM Research Report RC-240, J. T. Watson Research Center 1960
[21] Moon, On subtournaments of a tournament, Can Math Bull 9 (3) pp 297– (1966) · Zbl 0141.41204
[22] Moon, On maximal transitive subtournaments, Proc Edinburgh Math Soc 17 (4) pp 345– (1971) · Zbl 0234.05108
[23] Moon, On cliques in graphs, Israel J Math 3 pp 23– (1965) · Zbl 0144.23205
[24] Neumann’Lara, A short proof of a theorem of Reid and Parker on tournaments, Graphs Combin 10 pp 363– (1994) · Zbl 0811.05028
[25] Raman, Efficient exact algorithms through enumerating maximal independent sets and other techniques, Theor Comput Syst 41 (3) pp 563– (2007) · Zbl 1148.68054
[26] Rédei, Ein kombinatorischer Satz, Acta Litt Szeged 7 pp 39– (1934)
[27] Reed, Finding odd cycle transversals, Oper Res Lett 32 (4) pp 299– (2004) · Zbl 1052.05061
[28] Reid, Disproof of a conjecture of Erdos and Moser on tournaments, J Combin Theory 9 (3) pp 225– (1970) · Zbl 0204.24605
[29] Schwikowski, On enumerating all minimal solutions of feedback problems, Discrete Appl Math 117 pp 253– (2002) · Zbl 1004.68122
[30] Tsukiyama, A new algorithm for generating all the maximal independent sets, SIAM J Comput 6 (3) pp 505– (1977) · Zbl 0364.05027
[31] von Neumann, Theory of Games and Economic Behavior (1944)
[32] Woeginger, Exact algorithms for NP-hardproblems: a survey, in: Combinatorial Optimization - Eureka, You Shrink!, Vol. 2570 of Lecture Notes in Computer Science pp 185– (2003)
[33] Woeginger, Space and time complexity of exact algorithms: some open problems, in: Proceedings of IWPEC 2004, Vol. 3162 of Lecture Notes in Computer Science pp 281– (2004) · Zbl 1104.68520
[34] Woeginger, Open problems around exact algorithms, Discrete Appl Math 156 (3) pp 397– (2008) · Zbl 1165.90613
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.