TY - JOUR

T1 - The Complexity of Computing Minimal Unidirectional Covering Sets

AU - Baumeister, Dorothea

AU - Brandt, Felix

AU - Fischer, Felix

AU - Hoffmann, Jan

AU - Rothe, Jörg

N1 - Funding Information:
Acknowledgements This work was supported in part by DFG grants BR-2312/6-1, RO-1202/12-1 (within the European Science Foundation’s EUROCORES program LogICCC), BR 2312/3-2, RO-1202/11-1, and RO-1202/15-1, and by the Alexander von Humboldt Foundation’s TransCoop program. This work was done in part while the fifth author was visiting the University of Rochester.

PY - 2013/12

Y1 - 2013/12

N2 - A common thread in the social sciences is to identify sets of alternatives that satisfy certain notions of stability according to some binary dominance relation. Examples can be found in areas as diverse as voting theory, game theory, and argumentation theory. Brandt and Fischer (in Math. Soc. Sci. 56(2):254-268, 2008) proved that it is NP-hard to decide whether an alternative is contained in some inclusion-minimal unidirectional (i.e., either upward or downward) covering set. For both problems, we raise this lower bound to the Θ2p level of the polynomial hierarchy and provide a Σ2p upper bound. Relatedly, we show that a variety of other natural problems regarding minimal or minimum-size unidirectional covering sets are hard or complete for either of NP, coNP, and Θ2p. An important consequence of our results is that neither minimal upward nor minimal downward covering sets (even when guaranteed to exist) can be computed in polynomial time unless P=NP. This sharply contrasts with Brandt and Fischer's result that minimal bidirectional covering sets are polynomial-time computable.

AB - A common thread in the social sciences is to identify sets of alternatives that satisfy certain notions of stability according to some binary dominance relation. Examples can be found in areas as diverse as voting theory, game theory, and argumentation theory. Brandt and Fischer (in Math. Soc. Sci. 56(2):254-268, 2008) proved that it is NP-hard to decide whether an alternative is contained in some inclusion-minimal unidirectional (i.e., either upward or downward) covering set. For both problems, we raise this lower bound to the Θ2p level of the polynomial hierarchy and provide a Σ2p upper bound. Relatedly, we show that a variety of other natural problems regarding minimal or minimum-size unidirectional covering sets are hard or complete for either of NP, coNP, and Θ2p. An important consequence of our results is that neither minimal upward nor minimal downward covering sets (even when guaranteed to exist) can be computed in polynomial time unless P=NP. This sharply contrasts with Brandt and Fischer's result that minimal bidirectional covering sets are polynomial-time computable.

KW - Computational complexity

KW - Computational social choice

KW - Minimal downward covering sets

KW - Minimal upward covering sets

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

U2 - 10.1007/s00224-012-9437-9

DO - 10.1007/s00224-012-9437-9

M3 - Article

AN - SCOPUS:84879422247

SN - 1432-4350

VL - 53

SP - 467

EP - 502

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 3

ER -