[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Maximum Weight Independent Sets in Odd-Hole-Free Graphs Without Dart or Without Bull

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

The maximum weight independent set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated and most important problems on graphs, it is well known to be NP-complete and hard to approximate. The complexity of MWIS is open for hole-free graphs (i.e., graphs without induced subgraphs isomorphic to a chordless cycle of length at least five). By applying clique separator decomposition as well as modular decomposition, we obtain polynomial time solutions of MWIS for odd-hole- and dart-free graphs as well as for odd-hole- and bull-free graphs (dart and bull have five vertices, say \(a,b,c,d,e\), and dart has edges \(ab,ac,ad,bd,cd,de\), while bull has edges \(ab,bc,cd,be,ce\)). If the graphs are hole-free instead of odd-hole-free then stronger structural results and better time bounds are obtained.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Basavaraju, M., Chandran, L.S., Karthick, T.: Maximum weight independent sets in hole- and dart-free graphs. Discrete Appl. Math. 160, 2364–2369 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  2. Berry, A., Bordat, J.-P., Heggernes, P.: Recognizing weakly triangulated graphs by edge separability. Nord. J. Comput. 7, 164–177 (2000)

    MathSciNet  MATH  Google Scholar 

  3. Berry, A., Brandstädt, A., Giakoumakis, V., Maffray, F.: Efficiently recognizing, decomposing and triangulating hole- and diamond-free graphs, manuscript 2012; accepted for Discrete Appl. Math. (2012)

  4. Brandstädt, A.: (\(P_5\), diamond)-free graphs revisited: structure and linear time optimization. Discrete Appl. Math. 138, 13–27 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  5. Brandstädt, A., Giakoumakis, V.: Maximum weight independent sets in hole- and co-chair-free graphs. Inf. Process. Lett. 112, 67–71 (2012)

    Article  MATH  Google Scholar 

  6. Brandstädt, A., Giakoumakis, V., Maffray, F.: Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences. Discrete Appl. Math. 160, 471–478 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  7. Brandstädt, A., Hoàng, C.T., Le, V.B.: Stability number of bull- and chair-free graphs revisited. Discrete Appl. Math. 131, 39–50 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  8. Brandstädt, A., Klembt, T., Lozin, V.V., Mosca, R.: On independent vertex sets in subclasses of apple-free graphs. Algorithmica 56, 383–393 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  9. Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Math. Appl., Vol. 3. SIAM, Philadelphia (1999)

    Book  MATH  Google Scholar 

  10. Chudnovsky, M.: The structure of bull-free graphs II and III—A summary, J. Comb. Theory Ser. B 102, 252–282 (2012)

  11. Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., Vuskovič, K.: Recognizing Berge graphs. Combinatorica 25, 143–186 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  12. Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51–229 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  13. Chvátal, V., Fonlupt, J., Sun, L., Zemirline, A.: Recognizing dart-free perfect graphs. SIAM J. Comput. 31, 1315–1338 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  14. Conforti, M., Cornuéjols, G., Liu, X., Vuškovic, K., Zambelli, G.: Odd hole recognition in graphs of bounded clique size. SIAM J. Discrete Math. 20, 42–48 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  15. Cornuéjols, G., Liu, X., Vuškovic, K.: A polynomial algorithm for recognizing perfect graphs. In: Procedings 44th annals of IEEE symposium on foundations of computer science FOCS 2003, pp. 20–27 (2003)

  16. De Simone, C.: On the vertex packing problem. Graphs Comb. 9, 19–30 (1993)

    Article  MATH  Google Scholar 

  17. De Simone, C., Sassano, A.: Stability number of bull- and chair-free graphs. Discrete Appl. Math. 9, 121–129 (1993)

    Article  Google Scholar 

  18. De Figueiredo, C.M.H., Maffray, F., Porto, O.: On the structure of bull-free perfect graphs. Graphs Comb. 13, 31–55 (1997)

    Article  MATH  Google Scholar 

  19. Eschen, E.M., Sritharan, R.: A characterization of some graph classes with no long holes. J. Comb. Theory Ser. B 65, 156–162 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  20. Fricke, G.H., Hedetniemi, S.T., Jacobs, D.P.: Independence and irredundance in \(k\)-regular graphs. Ars Comb. 49, 271–279 (1998)

    MathSciNet  MATH  Google Scholar 

  21. Fouquet, J.-L.: A decomposition for a class of \((P_5,{\overline{P_5}})\)-free graphs. Discrete Math. 121, 75–83 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  22. Grötschel, M., Lovász, L., Schrijver, A.: Polynomial algorithms for perfect graphs. Ann. Discrete Math. 21, 325–356 (1984)

    Google Scholar 

  23. Hayward, R.B., Spinrad, J.B., Sritharan, R.: Improved algorithms for weakly chordal graphs, ACM Trans. Algorithms 3 (2007). Article 14

  24. McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math. 201, 189–241 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  25. Mosca, R.: Some results on maximum stable sets in certain \(P_5\)-free graphs. Discrete Appl. Math. 132, 175–183 (2004)

    Article  MathSciNet  Google Scholar 

  26. Penev, I.: Forbidden substructures in graphs and trigraphs, and related coloring problems, PhD Thesis, Columbia University (2012)

  27. Spinrad, J.P.: Finding large holes. Inf. Process. Lett. 39, 227–229 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  28. Spinrad, J.P., Sritharan, R.: Algorithms for weakly triangulated graphs. Discrete Appl. Math. 59, 181–191 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  29. Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55, 221–232 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  30. Thomassé, S., Trotignon, N., Vuskovič, K.: Parameterized algorithm for weighted independent set problem in bull-free graphs, Technical report 2013; available online

  31. Vuskovič, K.:Personal communication

  32. Whitesides, S.H.: A method for solving certain graph recognition and optimization problems, with applications to perfect graphs. In: Berge, C., Chvátal, V. (eds.) Topics on Perfect Graphs. North-Holland, Amsterdam (1984)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik, Universität Rostock, 18051, Rostock, Germany

    Andreas Brandstädt

  2. Dipartimento di Economia, Universitá degli Studi “G. d’Annunzio”, 65121, Pescara, Italy

    Raffaele Mosca

Authors
  1. Andreas Brandstädt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Raffaele Mosca
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Raffaele Mosca.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Brandstädt, A., Mosca, R. Maximum Weight Independent Sets in Odd-Hole-Free Graphs Without Dart or Without Bull. Graphs and Combinatorics 31, 1249–1262 (2015). https://doi.org/10.1007/s00373-014-1461-x

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-014-1461-x

Keywords

Search

Navigation