Ranking tournaments with no errors I: Structural description
Ranking tournaments with no errors I: Structural description
复制标题
无错误排名赛一：结构说明
DOI：
10.1016/j.jctb.2019.08.004
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zhao Qiulan
中科院分区：
文献类型：
--
作者：
Chen Xujin;Ding Guoli;Zang Wenan;Zhao Qiulan
在这一系列的两篇论文中，我们研究了经典的问题，排名一组球员的基础上产生的一组成对的比较，从一个体育锦标赛，目标是最大限度地减少总数量的不安，如果一个排名较高的球员实际上是由一个排名较低的球员击败了不安发生。这个问题可以被重新表述为所谓的最小反馈弧集问题的比赛，出现在各种各样的应用，并已被广泛研究的主题。在本系列中，我们使用结构驱动和线性规划方法来研究这个NP难问题。设T=（V，A）是一个在每条弧e上具有非负整数权w（e）的竞赛图.如果T\F不包含圈（有向），则弧的子集F称为反馈弧集。一个圈的集合C（允许重复）称为圈填充，如果每个弧e被C的成员最多使用w（e）次。我们称T为圈孟格尔（CM），如果对于定义在A上的每个非负整函数w，反馈弧集的最小总重量等于圈填充的最大尺寸。这两篇论文的目的是证明一个竞赛图是CM当且仅当它不包含四个莫比乌斯梯作为子图;这样的竞赛图被称为莫比乌斯自由图。在这第一篇论文中，我们提出了一个结构描述的所有莫比乌斯免费比赛，这在很大程度上依赖于链定理有关内部2-强比赛。
In this series of two papers we examine the classical problem of ranking a set of players on the basis of a set of pairwise comparisons arising from a sports tournament, with the objective of minimizing the total number of upsets, where an upset occurs if a higher ranked player was actually defeated by a lower ranked player. This problem can be rephrased as the so-called minimum feedback arc set problem on tournaments, which arises in a rich variety of applications and has been a subject of extensive research. In this series we study this NP-hard problem using structure-driven and linear programming approaches. Let T=(V, A) be a tournament with a nonnegative integral weight w (e) on each arc e. A subset F of arcs is called a feedback arc set if T\F contains no cycles (directed). A collection C of cycles (with repetition allowed) is called a cycle packing if each arc e is used at most w (e) times by members of C. We call T cycle Mengerian (CM) if, for every nonnegative integral function w defined on A, the minimum total weight of a feedback arc set is equal to the maximum size of a cycle packing. The purpose of these two papers is to show that a tournament is CM iff it contains none of four Möbius ladders as a subgraph; such a tournament is referred to as Möbius-free. In this first paper we present a structural description of all Möbius-free tournaments, which relies heavily on a chain theorem concerning internally 2-strong tournaments.