Computing the minimal covering set

Felix Brandt, Felix Fischer

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

Abstract

We present the first polynomial-time algorithm for computing the minimal covering set of a (weak) tournament. The algorithm draws upon a linear programming formulation of a subset of the minimal covering set known as the essential set. On the other hand, we show that no efficient algorithm exists for two variants of the minimal covering set-the minimal upward covering set and the minimal downward covering set-unless P equals NP. Finally, we observe a strong relationship between von Neumann-Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other.

Original languageEnglish
Pages (from-to)254-268
Number of pages15
JournalMathematical social sciences
Volume56
Issue number2
DOIs
StatePublished - Sep 2008
Externally publishedYes

Keywords

  • Computational complexity
  • Essential set
  • Minimal covering set
  • Social choice theory
  • Uncovered set

Fingerprint

Dive into the research topics of 'Computing the minimal covering set'. Together they form a unique fingerprint.

Cite this