Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T08:28:08.396Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  20 September 2006

PIERRE CHARBIT ,
STÉPHAN THOMASSÉ  and
ANDERS YEO
PIERRE CHARBIT
Affiliation:
Laboratoire Camille Jordan, Université Claude Bernard, Lyon 1, France (e-mail: charbit@univ-lyon1.fr, thomasse@univ-lyon1.fr)
STÉPHAN THOMASSÉ
Affiliation:
Laboratoire Camille Jordan, Université Claude Bernard, Lyon 1, France (e-mail: charbit@univ-lyon1.fr, thomasse@univ-lyon1.fr)
ANDERS YEO
Affiliation:
Department of Computer Science, Royal Holloway, University of London, Egham, Surrey TW20 0EX, UK (e-mail: anders@cs.rhul.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 1 , January 2007 , pp. 1 - 4
Copyright
© 2006 Cambridge University Press