Arora, PragyaPragyaAroraDey, PalashPalashDeyMisra, NeeldharaNeeldharaMisra2026-02-182026-02-182026-01-01[9789819571260]10.1007/978-981-95-7127-7_212-s2.0-105031247673https://repository.iitgn.ac.in/handle/IITG2025/34642We 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 Ω(n²) 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.en-USTournament solutionsQuery complexityNear-transitive tournamentsPseudo-transitive tournamentsCondorcetCopelandTop cycleUncovered setCondorcet | Copeland | Near-transitive tournaments | Pseudo-transitive tournaments | Query complexity | Top cycle | Tournament solutions | Uncovered setConference Paper16113349Conference PaperConference Paper