Feedback vertex sets in tournaments
From MaRDI portal
Publication:4908824
Abstract: We study combinatorial and algorithmic questions around minimal feedback vertex sets in tournament graphs. On the combinatorial side, we derive strong upper and lower bounds on the maximum number of minimal feedback vertex sets in an n-vertex tournament. We prove that every tournament on n vertices has at most 1.6740^n minimal feedback vertex sets, and that there is an infinite family of tournaments, all having at least 1.5448^n minimal feedback vertex sets. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal feedback vertex sets of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum size feedback vertex set in a tournament.
Recommendations
- Feedback vertex sets in tournaments
- Improved bounds for minimal feedback vertex sets in tournaments
- Improved Bounds for Minimal Feedback Vertex Sets in Tournaments
- Faster exact and parameterized algorithm for feedback vertex set in tournaments
- An approximation algorithm for feedback vertex sets in tournaments
Cites work
- scientific article; zbMATH DE number 1764950 (Why is no real title available?)
- A New Algorithm for Generating All the Maximal Independent Sets
- A note on the complexity of the chromatic number problem
- A short proof of a theorem of Reid and Parker on tournaments
- Combinatorial bounds via measure and conquer
- Disproof of a conjecture of Erdös and moser on tournaments
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- Enumerating maximal independent sets with applications to graph colouring.
- Feedback vertex sets in tournaments
- Finding induced subgraphs via minimal triangulations
- Finding odd cycle transversals.
- Iterative compression and exact algorithms
- Minimal stable sets in tournaments
- On Independent Sets and Bicliques in Graphs
- On Subtournaments of a Tournament
- On cliques in graphs
- On enumerating all minimal solutions of feedback problems
- On maximal transitive subtournaments
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- On the number of maximal bipartite subgraphs of a graph
- Open problems around exact algorithms
- Parameterized and Exact Computation
- Set partitioning via inclusion-exclusion
- Small Maximal Independent Sets and Faster Exact Graph Coloring
- Sophisticated voting outcomes and agenda control
- The Theory of Round Robin Tournaments
- Treewidth Computation and Extremal Combinatorics
Cited in
(19)- Faster exact and parameterized algorithm for feedback vertex set in tournaments
- Computing minimal extending sets by relation-algebraic modeling and development
- The PACE 2022 parameterized algorithms and computational experiments challenge: directed feedback vertex set
- Enumerating minimal connected dominating sets in graphs of bounded chordality
- Improved bounds for minimal feedback vertex sets in tournaments
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- When to Release Feedback in a Dynamic Tournament
- Enumeration and maximum number of minimal connected vertex covers in graphs
- 2-Approximating Feedback Vertex Set in Tournaments
- Maximal and maximum dissociation sets in general and triangle-free graphs
- Enumerating Minimal Tropical Connected Sets
- On the Number of Connected Sets in Bounded Degree Graphs
- Minimal dominating sets in interval graphs and trees
- Tournaments and Semicomplete Digraphs
- On the number of connected sets in bounded degree graphs
- Feedback arc number and feedback vertex number of Cartesian product of directed cycles
- Improved Bounds for Minimal Feedback Vertex Sets in Tournaments
- Feedback vertex sets in tournaments
- Bounds on the disparity and separation of tournament solutions
This page was built for publication: Feedback vertex sets in tournaments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4908824)
