Feedback arc set in bipartite tournaments is NP-complete
DOI10.1016/J.IPL.2006.11.016zbMATH Open1184.68264OpenAlexW2141319521MaRDI QIDQ845963FDOQ845963
Authors: Jiong Guo, Falk Hüffner, Hannes Moser 
Publication date: 29 January 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2006.11.016
Recommendations
- Feedback Arc Set Problem in Bipartite Tournaments
- Feedback arc set problem in bipartite tournaments
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- Fixed-parameter complexity of feedback vertex set in bipartite tournaments
- A polynomial kernel for Feedback Arc Set on bipartite tournaments
- A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
- A quadratic vertex kernel for feedback arc set in bipartite tournaments
- A quadratic vertex kernel for feedback arc set in bipartite tournaments
- Improved approximation algorithm for the feedback set problem in a bipartite tournament
- Fixed-parameter tractability results for feedback set problems in tournaments
Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Ranking Tournaments
- Structure preserving reductions among convex optimization problems
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- Feedback vertex sets and cyclically reducible graphs
- A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
- A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
- Aggregating inconsistent information
- Title not available (Why is that?)
- A Min-Max Theorem on Feedback Vertex Sets
- Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
Cited In (14)
- Tight upper bounds for minimum feedback arc sets of regular graphs
- Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
- Feedback arc set problem in bipartite tournaments
- Solving subgraph isomorphism problems with constraint programming
- Feedback arc set. A history of the problem and algorithms
- A better LP rounding for feedback arc set on tournaments
- A quadratic vertex kernel for feedback arc set in bipartite tournaments
- A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
- Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
- Computing the EHZ capacity is \(\operatorname{NP}\)-hard
- On the complexity of compressing two dimensional routing tables with order
- Forbidden tournaments and the orientation completion problem
- Fixed-parameter tractability results for feedback set problems in tournaments
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
This page was built for publication: Feedback arc set in bipartite tournaments is NP-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845963)
