The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments

Top Cited Papers

Publisher Website

20 September 2006

journal article
research article
Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing

Vol. 16 (01), 1-4
https://doi.org/10.1017/s0963548306007887

Abstract

Answering a question of Bang-Jensen and Thomassen [4], we prove that the minimum feedback arc set problem is NP-hard for tournaments.

Keywords

Cited by 90 articles