A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments

DOI10.1007/s00224-013-9453-4zbMath1277.05077OpenAlexW1990046850MaRDI 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

zbMATH Keywords

bipartite tournamentkernelizationfeedback arc set

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments

Cites Work

• Unnamed Item
• 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
• 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

This page was built for publication: A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments