Computing the minimal covering set

Felix Brandt and Felix Fischer

Mathematical Social Sciences, 2008, vol. 56, issue 2, 254-268

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.

Keywords: Social; choice; theory; Minimal; covering; set; Essential; set; Uncovered; set; Computational; complexity (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165-4896(08)00036-X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matsoc:v:56:y:2008:i:2:p:254-268

Access Statistics for this article

Mathematical Social Sciences is currently edited by J.-F. Laslier

More articles in Mathematical Social Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().