Tournaments as feedback arc sets
type: Item
instance of: scholarly article
title: Tournaments as feedback arc sets
zbMATH Open document ID: 0829.68100
author: Garth Isaak
published in: The Electronic Journal of Combinatorics
publication date: 1995-10-19T00:00:00Z
full work available at URL: https://eudml.org/doc/118763
full work available at URL: R20
review text: Summary: We examine the size \(s(n)\) of a smallest tournament having the arcs of an acyclic tournament on \(n\) vertices as a minimum feedback are set. Using an integer linear programming formulation we obtain lower bounds \(s(n) \geq 3n - 2 - \lfloor \log_2 n \rfloor\) or \(s(n) \geq 3n - 1 - \lfloor \log_2 n \rfloor\), depending on the binary expansion of \(n\). When \(n = 2^k - 2^t\) we show that the bounds are tight with \(s(n) = 3n - 2 - \lfloor \log_2 n \rfloor\). One view of this problem is that if the `teams' in a tournament are ranked to minimize inconsistencies there is some tournament with \(s(n)\) `teams' in which \(n\) are ranked wrong. We also pose some questions about conditions on feedback arc sets, motivated by our proofs, which ensure equality between the maximum number of arc disjoint cycles and the minimum size of a feedback arc set in a tournament.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 807685
zbMATH Keywords: tournament
zbMATH Keywords: feedback are set
zbMATH Keywords: integer linear programming
zbMATH Keywords: arc disjoint cycles
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 807685