1-Extendability of Independent Sets | Algorithmica Skip to main content
Springer Nature Link
Log in

1-Extendability of Independent Sets

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In the 70 s, Berge introduced 1-extendable graphs (also called B-graphs), which are graphs where every vertex belongs to a maximum independent set. Motivated by an application in the design of wireless networks, we study the computational complexity of 1-extendability, the problem of deciding whether a graph is 1-extendable. We show that, in general, 1-extendability cannot be solved in \(2^{o(n)}\) time assuming the Exponential Time Hypothesis, where n is the number of vertices of the input graph, and that it remains NP-hard in subcubic planar graphs and in unit disk graphs (which is a natural model for wireless networks). Although 1-extendability seems to be very close to the problem of finding an independent set of maximum size (a.k.a. Maximum Independent Set), we show that, interestingly, there exist 1-extendable graphs for which Maximum Independent Set is NP-hard. Finally, we investigate a parameterized version of 1-extendability.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

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

Similar content being viewed by others

References

  1. Alekseev, V.E.: The effect of local constraints on the complexity of determination of the graph independence number. Comb. Algebr. Methods Appl. Math. 3–13 (1982)

  2. Angaleeswari, K., Sumathi, P., Swaminathan, V.: \(k\)-extendability in graphs. Int. J. Pure Appl. Math. 101(5), 801–809 (2015)

    Google Scholar 

  3. Angaleeswari, K., Sumathi, P., Swaminathan, V.: Weakly \(k\)-extendable graphs. Int. J. Pure Appl. Math. 109(6), 35–40 (2016)

    Google Scholar 

  4. Berge, C.: Some common properties for regularizable graphs, edge-critical graphs and B-graphs. Graph Theory Algorithms Lect. Notes Comput. Sci. 108, 108–123 (1981)

    MathSciNet  Google Scholar 

  5. Bonnet, É., Bousquet, N., Charbit, P., Thomassé, S., Watrigant, R.: Parameterized complexity of independent set in \(H\)-free graphs. Algorithmica 82(8), 2360–2394 (2020)

    Article  MathSciNet  Google Scholar 

  6. Bonnet, É., Bousquet, N., Thomassé, S., Watrigant, R.: When maximum stable set can be solved in FPT time. Proc. ISAAC 149, 49:1-49:22 (2019)

    MathSciNet  Google Scholar 

  7. Chvátal, V., Slater, P. J.: A note on well-covered graphs. In: Quo Vadis, Graph Theory? Annals of Discrete Mathematics, vol. 55, pp. 179–181. Elsevier, Amsterdam (1993)

  8. Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discret. Math. 86(1–3), 165–177 (1990)

    Article  MathSciNet  Google Scholar 

  9. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)

    Book  Google Scholar 

  10. Dabrowski, K.K., Lozin, V.V., Müller, H., Rautenbach, D.: Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. J. Discrete Algorithms 14, 207–213 (2012)

    Article  MathSciNet  Google Scholar 

  11. de Berg, M., Khosravi, A.: Optimal binary space partitions in the plane. Proc. COCOON 6196, 216–225 (2010)

    MathSciNet  Google Scholar 

  12. Dean, N., Zito, J.S.: Well-covered graphs and extendability. Discret. Math. 126(1–3), 67–80 (1994)

    Article  MathSciNet  Google Scholar 

  13. Ducourthial, B., Mottelet, S., Busson, A.: Improving fairness between close Wi-Fi access points. J. Netw. Comput. Appl. 87, 87–99 (2017)

    Article  Google Scholar 

  14. Finbow, A.S., Whitehead, C.A.: Constructions for well-covered graphs. Austral. J. Comb. 72(2), 273–289 (2018)

    MathSciNet  Google Scholar 

  15. Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237–267 (1976)

    Article  MathSciNet  Google Scholar 

  16. Grzesik, A., Klimosová, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs. In: Proceedings of SODA, pp. 1257–1271. SIAM (2019)

  17. Hackfeld, J., Koster, A.: The matching extension problem in general graphs is co-NP-complete. J. Comb. Optim. 35(3), 853–859 (2018)

    Article  MathSciNet  Google Scholar 

  18. Impagliazzo, R., Paturi, R.: On the complexity of \(k\)-SAT. J. Comput. Syst. Sci. 62(2), 367–375 (2001)

    Article  MathSciNet  Google Scholar 

  19. Laufer, R., Kleinrock, L.: The capacity of wireless CSMA/CA networks. IEEE/ACM Trans. Netw. 24(3), 1518–1532 (2016)

    Article  Google Scholar 

  20. Liew, S.C., Kai, C.H., Leung, H.C., Wong, P.: Back-of-the-envelope computation of throughput distributions in CSMA wireless networks. IEEE Trans. Mobile Comput. 9(9), 1319–1331 (2010)

    Article  Google Scholar 

  21. Mohar, B.: Face covers and the genus problem for apex graphs. J. Comb. Theory Ser. B 82(1), 102–117 (2001)

    Article  ADS  MathSciNet  Google Scholar 

  22. Pilipczuk, M., Siebertz, S.: Kernelization and approximation of distance-r independent sets on nowhere dense graphs. Eur. J. Comb. 94, 103309 (2021)

    Article  MathSciNet  Google Scholar 

  23. Plummer, M.D.: Some covering concepts in graphs. J. Comb. Theory 8(1), 91–98 (1970)

    Article  MathSciNet  Google Scholar 

  24. Plummer, M.D.: On \(n\)-extendable graphs. Discrete Math. 31, 201–210 (1980)

    Article  MathSciNet  Google Scholar 

  25. Plummer, M.D.: Extending matchings in graphs: a survey. Discrete Math. 127(1–3), 277–292 (1994)

    Article  MathSciNet  Google Scholar 

  26. Poljak, S.: A note on stable sets and colorings in graphs. Comment. Math. Univ. Carol. 15, 307–309 (1974)

    Google Scholar 

  27. Ravindra, G.: B-graphs. In: Proceedings of the Symposium Graph Theory, ISI Lecture Notes Calcutta, 4, 268–280 (1976)

  28. Ravindra, G.: Well covered graphs. J. Comb. Inform. Syst. Sci. 2, 20–21 (1977)

    MathSciNet  Google Scholar 

  29. Sankaranarayana, R.S., Stewart, L.K.: Complexity results for well-covered graphs. Networks 22(3), 247–262 (1992)

    Article  MathSciNet  Google Scholar 

  30. Tankus, D., Tarsi, M.: Well-covered claw-free graphs. J. Comb. Theory Ser. B 66(2), 293–302 (1996)

    Article  MathSciNet  Google Scholar 

  31. The Network Simulator ns-3. https://www.nsnam.org/, 2022. Accessed on 30 Sept. 2021

  32. Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Comput. 30(2), 135–140 (1981)

    Article  MathSciNet  Google Scholar 

Download references

Funding

Partially supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007), and the research grant ANR DIGRAPHS ANR-19-CE48-0013-01, operated by the French National Research Agency (ANR).

Author information

Authors and Affiliations

  1. LIP UMR5668, Université Claude Bernard Lyon 1, ENS de Lyon, CNRS, Univ Lyon, Lyon, France

    Pierre Bergé, Anthony Busson, Carl Feghali & Rémi Watrigant

  2. LIMOS UMR 6158, CNRS, Université Clermont Auvergne, Clermont-Ferrand, France

    Pierre Bergé

Authors
  1. Pierre Bergé
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Anthony Busson
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Carl Feghali
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Rémi Watrigant
    View author publications

    You can also search for this author inPubMed Google Scholar

Contributions

All authors participated equally to this work.

Corresponding author

Correspondence to Rémi Watrigant.

Ethics declarations

Conflict of interest

The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bergé, P., Busson, A., Feghali, C. et al. 1-Extendability of Independent Sets. Algorithmica 86, 757–781 (2024). https://doi.org/10.1007/s00453-023-01138-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-023-01138-8

Keywords