Feedback arc set in bipartite tournaments is NP-complete

DOI10.1016/j.ipl.2006.11.016zbMath1184.68264MaRDI QIDQ845963

Jiong Guo, Hannes Moser, Falk Hüffner

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

zbMATH Keywords

computational complexity; combinatorial problems; bipartite tournaments; feedback set problems

Mathematics Subject Classification ID

68R05: Combinatorics in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)