Scholarlink

We study the query complexity of finding tournament solutions in near-transitive tournaments, which are tournaments obtained by flipping a small number of edges in a transitive tournament. While general tournaments require \(\varOmega (n^2)\) queries for many solution concepts such as Copeland, Top Cycle, and Uncovered Set, we show that we can do better for near-transitive tournaments in several scenarios. In particular, we introduce three query models: the standard model, where queries return orientations in the input tournament; the partial-flip model, where queries return orientations from the underlying transitive tournament and we have access to edge-flip queries; and the full-flip model, which additionally provides vertex-flip queries that indicate whether a vertex is incident to a flipped edge. Our main result shows that in the full-flip model, if at most \(\ell \) edges are flipped from a transitive tournament where \(\ell \leqslant \sqrt{n \log n}\) , then the set of Copeland winners, top cycle, and uncovered set can all be determined in \(O(n \log n)\) queries. This represents an improvement from the \(\varOmega (n^2)\) lower bound in general tournaments. We also show the fine-grained query complexity of obtaining Copeland winners parameterized by the number of flipped edges. Finally, we study pseudo-transitive tournaments—tournaments that are at most a single flip away from a transitive tournament—at length, and consider the query complexity of finding the Copeland winners, Top cycle, and Uncovered set in all three models. We also study the query complexity of determining if a pseudo-transitive tournament has a Condorcet winner in these models. Surprisingly, in the standard model, we need \(2n - \lceil \log n \rceil - 2 \) queries to determine if a pseudo-transitive tournament has a Condorcet winner: and these many queries are in fact sufficient to address the question on general tournaments, so the restriction to pseudo-transitive tournaments is not helpful. This situation persists in the partial-flip model, although we show an improved bound of \(n + \lceil \log n \rceil \) queries in the full-flip model.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Can One Flip Spoil it All?

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Pragya Arora,
  • Palash Dey,
  • Neeldhara Misra

摘要

We study the query complexity of finding tournament solutions in near-transitive tournaments, which are tournaments obtained by flipping a small number of edges in a transitive tournament. While general tournaments require \(\varOmega (n^2)\) queries for many solution concepts such as Copeland, Top Cycle, and Uncovered Set, we show that we can do better for near-transitive tournaments in several scenarios. In particular, we introduce three query models: the standard model, where queries return orientations in the input tournament; the partial-flip model, where queries return orientations from the underlying transitive tournament and we have access to edge-flip queries; and the full-flip model, which additionally provides vertex-flip queries that indicate whether a vertex is incident to a flipped edge. Our main result shows that in the full-flip model, if at most \(\ell \) edges are flipped from a transitive tournament where \(\ell \leqslant \sqrt{n \log n}\) , then the set of Copeland winners, top cycle, and uncovered set can all be determined in \(O(n \log n)\) queries. This represents an improvement from the \(\varOmega (n^2)\) lower bound in general tournaments. We also show the fine-grained query complexity of obtaining Copeland winners parameterized by the number of flipped edges. Finally, we study pseudo-transitive tournaments—tournaments that are at most a single flip away from a transitive tournament—at length, and consider the query complexity of finding the Copeland winners, Top cycle, and Uncovered set in all three models. We also study the query complexity of determining if a pseudo-transitive tournament has a Condorcet winner in these models. Surprisingly, in the standard model, we need \(2n - \lceil \log n \rceil - 2 \) queries to determine if a pseudo-transitive tournament has a Condorcet winner: and these many queries are in fact sufficient to address the question on general tournaments, so the restriction to pseudo-transitive tournaments is not helpful. This situation persists in the partial-flip model, although we show an improved bound of \(n + \lceil \log n \rceil \) queries in the full-flip model.