Feedback arc set in bipartite tournaments is NP-complete
From MaRDI portal
Publication:845963
DOI10.1016/j.ipl.2006.11.016zbMath1184.68264OpenAlexW2141319521MaRDI QIDQ845963
Falk Hüffner, Jiong Guo, 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
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)
Related Items (8)
Feedback arc set problem in bipartite tournaments ⋮ Solving subgraph isomorphism problems with constraint programming ⋮ A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments ⋮ On the complexity of compressing two dimensional routing tables with order ⋮ Linear programming based approximation algorithms for feedback set problems in bipartite tournaments ⋮ A quadratic vertex kernel for feedback arc set in bipartite tournaments ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
Cites Work
- Unnamed Item
- Structure preserving reductions among convex optimization problems
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- Fixed-Parameter Tractability Results for Feedback Set Problems in 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
- Ranking Tournaments
- A Min-Max Theorem on Feedback Vertex Sets
- Aggregating inconsistent information
This page was built for publication: Feedback arc set in bipartite tournaments is NP-complete
