Skip to main content
SpringerLink
Log in

Finding small stabilizers for unstable graphs

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

An undirected graph \(G=(V,E)\) is stable if the cardinality of a maximum matching equals the size of a minimum fractional vertex cover. We call a set of edges \(F \subseteq E\) a stabilizer if its removal from \(G\) yields a stable graph. In this paper we study the following natural edge-deletion question: given a graph \(G=(V,E)\), can we find a minimum-cardinality stabilizer? Stable graphs play an important role in cooperative game theory. In the classic matching game introduced by Shapley and Shubik (Int J Game Theory 1(1):111–130, 1971) we are given an undirected graph \(G=(V,E)\) where vertices represent players, and we define the value of each subset \(S \subseteq V\) as the cardinality of a maximum matching in the subgraph induced by \(S\). The core of such a game contains all fair allocations of the value of \(V\) among the players, and is well-known to be non-empty iff graph \(G\) is stable. The stabilizer problem addresses the question of how to modify the graph to ensure that the core is non-empty. We show that this problem is vertex-cover hard. We prove that every minimum-cardinality stabilizer avoids some maximum matching of \(G\). We use this insight to give efficient approximation algorithms for sparse graphs and for regular graphs.

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

Access this article

Log in via an institution

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

Similar content being viewed by others

References

  1. Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: \(O(\sqrt{\log n})\) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. In: Proceedings, ACM Symposium on Theory of Computing, pp. 573–581 (2005)

  2. Alon, Noga, Shapira, Asaf, Sudakov, Benny: Additive approximation for edge-deletion problems. Ann. Math. 170, 371–411 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  3. Balas, E.: Integer and fractional matchings. Ann. Discrete Math. 11, 1–13 (1981)

    MATH  MathSciNet  Google Scholar 

  4. Balinski, M.L.: On maximum matching, minimum covering and their connections. In: Proceedings of the Princeton Symposium on Mathematical Programming (1970)

  5. Bateni, M., Hajiaghayi, M., Immorlica, N., Mahini, H.: The cooperative game theory foundations of network bargaining games. In: Proceedings of International Colloquium on Automata, Languages and Processing, pp. 67–78 (2010)

  6. Biró, P., Bomhoff, M., Golovach, P.A., Kern, W., Paulusma, D.: Solutions for the stable roommates problem with payments. Theor. Comp. Sci. 540–541, 53–61 (2014). http://www.sciencedirect.com/science/article/pii/S030439751300251X

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

  8. Cook, W., Cunningham, W., Pulleyblank, W., Schrijver, A.: Combinatorial Optimization. Wiley, New York (1998)

    MATH  Google Scholar 

  9. Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439–485 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  10. Hochbaum, D.: Approximation algorithms for the set covering and vertex cover problems. SIAM J Comput 11(3), 555–556 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  11. Khot, S.: On the power of unique 2-Prover 1-Round games. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 767–775 (2002)

  12. Khot, S., Regev, O.: Vertex cover might be hard to approximate to within \(2-\varepsilon \). J. Comput. Syst. Sci. 74, 335–349 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  13. Kleinberg, J.M., Tardos, É.: Balanced outcomes in social exchange networks. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 295–304 (2008)

  14. Könemann, J., Larson, K., Steiner, D.: Network bargaining: using approximate blocking sets to stabilize unstable instances. In: Proceedings of the Symposium on Algorithmic Game Theory, pp. 216–226 (2012)

  15. Korach, E., Nguyen, T., Peis, B.: Subgraph characterization of red/blue-split graph and König Egerváry graphs. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 842–850 (2006)

  16. Korach, E.: Flowers and Trees in a Ballet of \(K_4\), or a Finite Basis Characterization of Non-König–Egerváry Graphs, Tech. Rep. 115. IBM Israel Scientific Center (1982)

  17. Lovász, L.: A note on factor-critical graphs. Studia Sci. Math. Hungar. 7, 279–280 (1972)

    MathSciNet  Google Scholar 

  18. Mishra, S., Raman, V., Saurabh, S., Sikdar, S., Subramanian, C.R.: The complexity of König subgraph problems and above-guarantee vertex cover. Algorithmica 61(4), 857–881 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  19. Nash, J.: The bargaining problem. Econometrica 18, 155–162 (1950)

    Article  MATH  MathSciNet  Google Scholar 

  20. Pulleyblank, W.R.: Fractional matchings and the Edmonds–Gallai theorem. Discrete Appl. Math. 16, 51–58 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  21. Schrijver, A.: Combinatorial Optimization. Springer, New York (2003)

    MATH  Google Scholar 

  22. Shapley, L.S., Shubik, M.: The assignment game: the core. Int. J. Game Theory 1(1), 111–130 (1971)

    Article  MATH  MathSciNet  Google Scholar 

  23. Sterboul, F.: A characterization of the graphs in which the transversal number equals the matching number. J. Combin. Theory Ser. B 27(2), 228–229 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  24. Uhry, J.P.: Sur le problème du couplage maximal. RAIRO 3, 13–20 (1975)

    MathSciNet  Google Scholar 

  25. Yannakakis, M.: Node- and edge-deletion NP-complete problems. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 253–264 (1978)

Download references

Author information

Authors and Affiliations

  1. EPFL, Lausanne, Switzerland

    Adrian Bock

  2. University of Illinois at Urbana-Champaign, Champaign, IL, USA

    Karthekeyan Chandrasekaran

  3. University of Waterloo, Waterloo, Canada

    Jochen Könemann & Laura Sanità

  4. RWTH Aachen University, Aachen, Germany

    Britta Peis

Authors
  1. Adrian Bock
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Karthekeyan Chandrasekaran
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jochen Könemann
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Britta Peis
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Laura Sanità
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Karthekeyan Chandrasekaran.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bock, A., Chandrasekaran, K., Könemann, J. et al. Finding small stabilizers for unstable graphs. Math. Program. 154, 173–196 (2015). https://doi.org/10.1007/s10107-014-0854-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-014-0854-1

Keywords

Mathematics Subject Classification

Search

Navigation