Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The Complexity of Computing Minimal Unidirectional Covering Sets

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

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 \(\varTheta_{2}^{p}\) level of the polynomial hierarchy and provide a \(\varSigma_{2}^{p}\) 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 \(\varTheta_{2}^{p}\). 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. Such payoff vectors are called imputations; see, e.g., [12, 40] for the game-theoretic notions not defined here.

  2. In general, ≻ need not be transitive or complete. For alternatives x and y, x≻y (equivalently, (x,y)∈ ≻) is interpreted as x being strictly preferred to y (and we say “x dominates y”), e.g., due to a strict majority of voters preferring x to y (recall Fig. 1 for an example).

  3. Consider the set A={a,b,c} of three alternatives with the dominance relation defined by a≻b≻c. Note that A is not a downward covering set for itself, since it violates internal stability (UC d (A)={a,b}≠A, due to c being downward covered by b in A); both {a,b} and {b,c} violate internal stability as well (e.g., UC d ({a,b})={a}≠{a,b}); and external stability is violated by {a,c} (due to b∈UC d ({a,c}∪{b})=UC d (A)={a,b}), each singleton (c∈UC d ({a}∪{c})={a,c} shows this for {a}, a∈UC d ({b}∪{a})={a} works for {b}, and b∈UC d ({c}∪{b})={b} works for {c}), and the empty set (due to, e.g., a∈UC d (∅∪{a})={a}). Thus A has no downward covering set at all.

  4. Consider, for example, the set A={a,b,c,d,e} of five alternatives with the dominance relation defined by a≻b≻c≻d≻a and b≻e. It is easy to see that both {a,c,e} and {b,d} are minimal upward covering sets for A, but only {b,d} is an upward covering set of minimum size for A. That is, {a,c,e} is a minimal, but not minimum-size upward covering set for A.

  5. This type of reduction was introduced by Ladner et al. [32]. Informally stated, a disjunctive truth-table reduction between two decision problems X and Y computes, given an instance x, in polynomial time k queries y 1,y 2,…,y k such that x∈X if and only if y i ∈Y for at least one i, 1≤i≤k. This reduction can be adapted straightforwardly to function problems F and G: F disjunctively truth-table reduces to G if, given an instance x, in polynomial time we can compute k queries y 1,y 2,…,y k such that F(x) can be computed from G(y i ) for at least one i, 1≤i≤k.

  6. The argument is analogous to that used in the construction of Brandt and Fischer [7] in their proof of Theorem 2. However, in contrast with their construction, which implies that either \(\{x_{i}, x'_{i}\}\) or \(\{\overline{x}_{i}, \overline{x}'_{i}\}\) , 1≤i≤n, but not both, must be contained in any minimal upward covering set for A (see Fig. 2), our construction also allows for both \(\{u_{i}, u'_{i}\}\) and \(\{\overline{u}_{i}, \overline{u}'_{i}\}\) being contained in some minimal upward covering set for A. Informally stated, the reason is that, unlike the four-cycles in Fig. 2, our four-cycles \(u_{i} \succ\overline{u}_{i} \succ u'_{i} \succ\overline{u}'_{i} \succ u_{i}\) also have incoming edges.

  7. For example, recall Wagner’s \(\varTheta_{2}^{p}\)-completeness result for testing whether the size of a maximum clique in a given graph is an odd number [51]. One key ingredient in his proof is to define an associative operation on graphs, ⋈, such that for any two graphs G and H, the size of a maximum clique in G⋈H equals the sum of the sizes of a maximum clique in G and one in H. This operation is quite simple: Just connect every vertex of G with every vertex of H. In contrast, since minimality for minimal upward covering sets is defined in terms of set inclusion, it is not at all obvious how to define a similarly simple operation on dominance graphs such that the minimal upward covering sets in the given graphs are related to the minimal upward covering sets in the connected graph in a similarly useful way.

  8. Our argument about \((B_{i}, \succ_{i}^{B})\) can be used to show, in effect, DP-hardness of upward covering set problems, where DP is the class of differences of any two NP sets [42]. Note that DP is the second level of the boolean hierarchy over NP (see Cai et al. [10, 11]), and it holds that \(\mathrm {NP}\cup \mathrm {coNP}\subseteq \mathrm {DP}\subseteq \varTheta_{2}^{p}\). Wagner [51] proved appropriate analogs of Lemma 1 for each level of the boolean hierarchy. In particular, the analogous criterion for DP-hardness is obtained by using the wording of Lemma 1 except with the value of m=1 being fixed.

  9. This implies that d 1 is not upward covered by either \(u_{1,2}'\) or \(\overline{u}_{1,2}'\), since d 3 dominates them both but not d 1.

  10. This is different from the case of minimum-size upward covering sets for the dominance graph constructed in the proof sketch of Theorem 2. The construction in the proof sketch of Theorem 18 cannot be used to obtain complexity results for minimum-size downward covering sets in the same way as the construction in the proof sketch of Theorem 2 was used to obtain complexity results for minimum-size upward covering sets.

References

  1. Adleman, L.: Two theorems on random polynomial time. In: Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, pp. 75–83 (1978)

    Google Scholar 

  2. Alon, N.: Ranking tournaments. SIAM J. Discrete Math. 20(1), 137–142 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  3. Baumeister, D., Brandt, F., Fischer, F., Hoffmann, J., Rothe, J.: The complexity of computing minimal unidirectional covering sets. In: Proceedings of the 7th International Conference on Algorithms and Complexity. Lecture Notes in Computer Science, vol. 6078, pp. 299–310. Springer, Berlin (2010)

    Chapter  Google Scholar 

  4. Black, D.: The Theory of Committees and Elections. Cambridge University Press, Cambridge (1958)

    MATH  Google Scholar 

  5. Bordes, G.: On the possibility of reasonable consistent majoritarian choice: some positive results. J. Econ. Theory 31, 122–132 (1983)

    Article  MATH  Google Scholar 

  6. Bouveret, S., Lang, J.: Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity. J. Artif. Intell. Res. 32, 525–564 (2008)

    MathSciNet  MATH  Google Scholar 

  7. Brandt, F., Fischer, F.: Computing the minimal covering set. Math. Soc. Sci. 56(2), 254–268 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  8. Brandt, F., Fischer, F., Harrenstein, P.: The computational complexity of choice sets. Math. Log. Q. 55(4), 444–459 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  9. Brandt, F., Fischer, F., Harrenstein, P., Mair, M.: A computational analysis of the tournament equilibrium set. Soc. Choice Welf. 34(4), 597–609 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  10. Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The boolean hierarchy I: structural properties. SIAM J. Comput. 17(6), 1232–1252 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  11. Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The boolean hierarchy II: applications. SIAM J. Comput. 18(1), 95–111 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  12. Chalkiadakis, G., Elkind, E., Wooldridge, M.: Computational Aspects of Cooperative Game Theory. Synthesis Lectures on Artificial Intelligence and Machine Learning. (2011). Morgan & Claypool Publishers

    Google Scholar 

  13. de Condorcet, M.: Essai sur L’application de L’analyse à la Probabilité des Décisions Rendues à la Pluralité des Voix. Imprimerie Royale, Paris (1785). Facsimile published in 1972 by Chelsea, New York

    Google Scholar 

  14. Conitzer, V.: Computing slater rankings using similarities among candidates. In: Proceedings of the 21st National Conference on Artificial Intelligence, pp. 613–619. AAAI Press, Menlo Park (2006)

    Google Scholar 

  15. Dodgson, C.: A method of taking votes on more than two issues (1876). Pamphlet printed by the Clarendon Press, Oxford, and headed “not yet published” (see the discussions in [4, 37], both of which reprint this paper)

  16. Dutta, B.: Covering sets and a new Condorcet choice correspondence. J. Econ. Theory 44, 63–80 (1988)

    Article  MATH  Google Scholar 

  17. Eiter, T., Gottlob, G.: Propositional circumscription and extended closed-world reasoning are \(\varPi_{2}^{p}\)-complete. Theor. Comput. Sci. 114(2), 231–245 (1993). Addendum appears in the same journal, 118(2):315, 1993

    Article  MathSciNet  MATH  Google Scholar 

  18. Eiter, T., Gottlob, G.: On the computational cost of disjunctive logic programming: propositional case. Ann. Math. Artif. Intell. 15(3–4), 289–323 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  19. Eiter, T., Gottlob, G.: The complexity class \(\varTheta^{p}_{2}\): recent results and applications. In: Proceedings of the 11th Conference on Fundamentals of Computation Theory. Lecture Notes in Computer Science, vol. 1279, pp. 1–18. Springer, Berlin (1997)

    Chapter  Google Scholar 

  20. Fishburn, P.: Condorcet social choice functions. SIAM J. Appl. Math. 33(3), 469–489 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  21. Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)

    MATH  Google Scholar 

  22. Hemachandra, L.: The strong exponential hierarchy collapses. In: Proceedings of the 19th ACM Symposium on Theory of Computing, pp. 110–122. ACM, New York (1987)

    Google Scholar 

  23. Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. J. ACM 44(6), 806–825 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  24. Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Raising NP lower bounds to parallel NP lower bounds. SIGACT News 28(2), 2–13 (1997)

    Article  Google Scholar 

  25. Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Hybrid elections broaden complexity-theoretic resistance to control. Tech. Rep. arXiv:cs/0608057v2 [cs.GT], ACM Computing Research Repository (CoRR) (2008). Conference version appeared in Proc. IJCAI’07. Journal version to appear in Math. Logic Q., 55(4):397–424, (2009)

  26. Hemaspaandra, E., Rothe, J.: Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP. Inf. Process. Lett. 65(3), 151–156 (1998)

    Article  MathSciNet  Google Scholar 

  27. Hemaspaandra, E., Rothe, J., Spakowski, H.: Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP. RAIRO Theor. Inform. Appl. 40(1), 75–91 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  28. Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of Kemeny elections. Theor. Comput. Sci. 349(3), 382–391 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  29. Hemaspaandra, E., Wechsung, G.: The minimization problem for boolean formulas. SIAM J. Comput. 31(6), 1948–1958 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  30. Kemeny, J.: Mathematics without numbers. Dædalus 88, 571–591 (1959)

    Google Scholar 

  31. Köbler, J., Schöning, U., Wagner, K.: The difference and truth-table hierarchies for NP. RAIRO Theor. Inform. Appl. 21, 419–435 (1987)

    MATH  Google Scholar 

  32. Ladner, R., Lynch, N., Selman, A.: A comparison of polynomial time reducibilities. Theor. Comput. Sci. 1(2), 103–124 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  33. Laslier, J.: Tournament Solutions and Majority Voting. Springer, Berlin (1997)

    Book  MATH  Google Scholar 

  34. Lucas, W.: The proof that a game may not have a solution. Trans. Am. Math. Soc. 136, 219–229 (1969)

    Article  Google Scholar 

  35. Lucas, W.: Von Neumann–Morgenstern stable sets. In: Handbook of Game Theory, vol. 1. Elsevier, Amsterdam (1992)

    Google Scholar 

  36. McGarvey, D.: A theorem on the construction of voting paradoxes. Econometrica 21(4), 608–610 (1953)

    Article  MathSciNet  Google Scholar 

  37. McLean, I., Urken, A.: Classics of Social Choice. University of Michigan Press, Ann Arbor (1995)

    Google Scholar 

  38. Meyer, A., Stockmeyer, L.: The equivalence problem for regular expressions with squaring requires exponential space. In: Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, pp. 125–129 (1972)

    Chapter  Google Scholar 

  39. Miller, N.: A new solution set for tournaments and majority voting: further graph-theoretical approaches to the theory of voting. Am. J. Polit. Sci. 24(1), 68–96 (1980)

    Article  Google Scholar 

  40. von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton (1944)

    MATH  Google Scholar 

  41. Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)

    MATH  Google Scholar 

  42. Papadimitriou, C., Yannakakis, M.: The complexity of facets (and some facets of complexity). J. Comput. Syst. Sci. 28(2), 244–259 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  43. Papadimitriou, C., Zachos, S.: Two remarks on the power of counting. In: Proceedings of the 6th GI Conference on Theoretical Computer Science. Lecture Notes in Computer Science, vol. 145, pp. 269–276. Springer, Berlin (1983)

    Chapter  Google Scholar 

  44. Rothe, J.: Complexity Theory and Cryptology. An Introduction to Cryptocomplexity. EATCS Texts in Theoretical Computer Science. Springer, Berlin (2005)

    MATH  Google Scholar 

  45. Rothe, J., Spakowski, H., Vogel, J.: Exact complexity of the winner problem for Young elections. Theory Comput. Syst. 36(4), 375–386 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  46. Schaefer, M., Umans, C.: Completeness in the polynomial-time hierarchy. Part I: A compendium. SIGACT News 33(3), 32–49 (2002)

    Article  Google Scholar 

  47. Schaefer, M., Umans, C.: Completeness in the polynomial-time hierarchy. Part II. SIGACT News 33(4), 22–36 (2002)

    Article  Google Scholar 

  48. Stockmeyer, L.: The polynomial-time hierarchy. Theor. Comput. Sci. 3(1), 1–22 (1976)

    Article  MathSciNet  Google Scholar 

  49. Umans, C.: The minimum equivalent DNF problem and shortest implicants. J. Comput. Syst. Sci. 63(4), 597–611 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  50. Valiant, L.: The relative complexity of checking and evaluating. Inf. Process. Lett. 5(1), 20–23 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  51. Wagner, K.: More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci. 51, 53–80 (1987)

    Article  MATH  Google Scholar 

  52. Wagner, K.: Bounded query classes. SIAM J. Comput. 19(5), 833–846 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  53. Woeginger, G.: Banks winners in tournaments are difficult to recognize. Soc. Choice Welf. 20, 523–528 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  54. Young, H.: Extending Condorcet’s rule. J. Econ. Theory 16(2), 335–353 (1977)

    Article  MATH  Google Scholar 

Download references

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.

Author information

Authors and Affiliations

  1. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, 40225, Düsseldorf, Germany

    Dorothea Baumeister & Jörg Rothe

  2. Institut für Informatik, Technische Universität München, 85748, Garching, Germany

    Felix Brandt

  3. Statistical Laboratory, University of Cambridge, Cambridge, CB3 0WB, UK

    Felix Fischer

  4. Department of Computer Science, Yale University, New Haven, CT, 06511, USA

    Jan Hoffmann

Authors
  1. Dorothea Baumeister
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Felix Brandt
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Felix Fischer
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jan Hoffmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jörg Rothe
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dorothea Baumeister.

Additional information

A preliminary version of this paper appeared in the Proceedings of the Seventh International Conference on Algorithms and Complexity (CIAC-2010) [3].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Baumeister, D., Brandt, F., Fischer, F. et al. The Complexity of Computing Minimal Unidirectional Covering Sets. Theory Comput Syst 53, 467–502 (2013). https://doi.org/10.1007/s00224-012-9437-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-012-9437-9

Keywords

Search

Navigation