A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
From MaRDI portal
Publication:385516
DOI10.1007/s00224-013-9453-4zbMath1277.05077MaRDI QIDQ385516
Venkatesh Raman, Saket Saurabh, Pranabendu Misra, M. S. Ramanujan
Publication date: 2 December 2013
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-013-9453-4
05C38: Paths and cycles
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C20: Directed graphs (digraphs), tournaments
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A survey of the algorithmic aspects of modular decomposition
- Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Feedback arc set in bipartite tournaments is NP-complete
- A kernelization algorithm for \(d\)-hitting set
- A more effective linear kernelization for cluster editing
- On problems without polynomial kernels
- Fixed-parameter tractability results for feedback set problems in tournaments
- Feedback arc set problem in bipartite tournaments
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments
- Kernels for Feedback Arc Set In Tournaments
- A 4 k 2 kernel for feedback vertex set
- Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
- A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Fast FAST
- Incompressibility through Colors and IDs
- A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
- (Meta) Kernelization
- Bidimensionality and Geometric Graphs
- Ranking Tournaments
- Digraphs
- A Min-Max Theorem on Feedback Vertex Sets
- Aggregating inconsistent information
