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

Journal article

Open access

Peer reviewed

Pierre Charbit, Stéphan Thomassé and Anders Yeo

Combinatorics, Probability and Computing, Vol.16, pp.01-04

01/2007

Abstract

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

url

Find in HALView

1 Record Views

Title: The Minimum Feedback Arc Set Problem is NP-hard for Tournaments
Creators - without role: Pierre Charbit - Université Claude Bernard Lyon 1
Stéphan Thomassé - Université Claude Bernard Lyon 1
Anders Yeo - Royal Holloway University of London
Publication Details: Combinatorics, Probability and Computing, Vol.16, pp.01-04
Identifiers: 9942042609311
Academic Unit: Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
Language: English
Resource Type: Journal article
Local Fields: lirmm-00140321