Computing the minimal covering set

Felix Brandt; Felix Fischer

doi:10.1016/j.mathsocsci.2008.04.001

Computing the minimal covering set

Felix Brandt, Felix Fischer

University of Munich

Research output: Contribution to journal › Article › peer-review

37 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 language	English
Pages (from-to)	254-268
Number of pages	15
Journal	Mathematical social sciences
Volume	56
Issue number	2
DOIs	https://doi.org/10.1016/j.mathsocsci.2008.04.001
State	Published - Sep 2008
Externally published	Yes

Keywords

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

Access to Document

10.1016/j.mathsocsci.2008.04.001

Cite this

@article{731d1c2d0ccd4c40ba5377e625ddca84,

title = "Computing the minimal covering set",

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 = "Computational complexity, Essential set, Minimal covering set, Social choice theory, Uncovered set",

author = "Felix Brandt and Felix Fischer",

note = "Funding Information: This material is based upon work supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/3-1. Earlier versions of this paper were presented at the 5th International Conference on Logic, Game Theory and Social Choice (LGS), the 22nd Conference on Artificial Intelligence (AAAI), and the Dagstuhl Seminar on Computational Issues in Social Choice. ",

year = "2008",

month = sep,

doi = "10.1016/j.mathsocsci.2008.04.001",

language = "English",

volume = "56",

pages = "254--268",

journal = "Mathematical social sciences",

issn = "0165-4896",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Computing the minimal covering set

AU - Brandt, Felix

AU - Fischer, Felix

N1 - Funding Information: This material is based upon work supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/3-1. Earlier versions of this paper were presented at the 5th International Conference on Logic, Game Theory and Social Choice (LGS), the 22nd Conference on Artificial Intelligence (AAAI), and the Dagstuhl Seminar on Computational Issues in Social Choice.

PY - 2008/9

Y1 - 2008/9

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Essential set

KW - Minimal covering set

KW - Social choice theory

KW - Uncovered set

UR - http://www.scopus.com/inward/record.url?scp=48449084604&partnerID=8YFLogxK

U2 - 10.1016/j.mathsocsci.2008.04.001

DO - 10.1016/j.mathsocsci.2008.04.001

M3 - Article

AN - SCOPUS:48449084604

SN - 0165-4896

VL - 56

SP - 254

EP - 268

JO - Mathematical social sciences

JF - Mathematical social sciences

IS - 2

ER -

Computing the minimal covering set

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this