Complete classification of tournaments having a disjoint union of directed paths as a minimum feedback arc set
✍ Scribed by Garth Isaak; Darren A. Narayan
- Publisher
- John Wiley and Sons
- Year
- 2003
- Tongue
- English
- Weight
- 199 KB
- Volume
- 45
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
A feedback arc set of a digraph is a set of arcs whose reversal makes the resulting digraph acyclic. Given a tournament with a disjoint union of directed paths as a feedback arc set, we present necessary and sufficient conditions for this feedback arc set to have minimum size. We will present a construction for tournaments where the difference between the size of a minimum feedback arc set and the size of the largest collection of arc disjoint cycles can be made arbitrarily large. We will also make a connection to a problem found in [Barthélemy et al., 2]. The reversing number of a digraph was defined to be $r(D), = |V(T)|-|V(D)|$ where T is a smallest tournament having the arc set of D as a minimum feedback arc set. As a consequence of our classification of all tournaments having a disjoint union of directed paths as a minimum feedback arc set, we will obtain a new result involving the reversing number. We obtain precise reversing numbers for all digraphs consisting of a disjoint union of directed paths. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 28–47, 2004