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

Critical hereditary graph classes: a survey

  • Review Article
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

The task of complete complexity dichotomy is to clearly distinguish between easy and hard cases of a given problem on a family of subproblems. We consider this task for some optimization problems restricted to certain classes of graphs closed under deletion of vertices. A concept in the solution process is based on revealing the so-called “critical” graph classes, which play an important role in the complexity analysis for the family. Recent progress in studying such classes is presented in the article.

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
Fig. 9
Fig. 10

Similar content being viewed by others

References

  1. Abou Eisha, H., Hussain, S., Lozin, V., Monnot, J., Ries, B.: A dichotomy for upper domination in monogenic classes. Lect. Notes Comput. Sci. 8881, 258–267 (2014)

  2. Alekseev, V.: On easy and hard hereditary classes of graphs with respect to the independent set problem. Discrete Appl. Math. 132, 17–26 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  3. Alekseev, V.: Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Appl. Math. 135, 3–16 (2004)

    Article  MathSciNet  Google Scholar 

  4. Alekseev, V., Boliac, R., Korobitsyn, D., Lozin, V.: NP-hard graph problems and boundary classes of graphs. Theor. Comput. Sci. 389, 219–236 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  5. Alekseev, V., Korobitsyn, D., Lozin, V.: Boundary classes of graphs for the dominating set problem. Discrete Math. 285, 1–6 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  6. Alekseev, V., Lozin, V., Malyshev, D., Milanic, M.: The maximum independent set problem in planar graphs. Lect. Notes Comput. Sci. 5162, 96–107 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  7. Alekseev, V., Malyshev, D.: Planar graph classes with the independent set problem solvable in polynomial time. J. Appl. Ind. Math. 3, 1–4 (2009)

    Article  MathSciNet  Google Scholar 

  8. Boliac, R., Lozin, V.: On the clique-width of graphs in hereditary classes. Lect. Notes Comput. Sci. 2518, 44–54 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  9. Broersma, H., Golovach, P., Paulusma, D., Song, J.: Updating the complexity status of coloring graphs without a fixed induced linear forest. Theor. Comput. Sci. 414, 9–19 (2012)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  11. Courcelle, B., Makowsky, J., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33, 125–150 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  12. Dereniowski, D.: Edge ranking of weighted trees. Discrete Appl. Math. 154, 1198–1209 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  13. Dereniowski, D.: The complexity of list ranking of trees. Ars Comb. 86, 97–114 (2008)

    MathSciNet  MATH  Google Scholar 

  14. Garey, M., Johnson, D.: Computers and intractability: a guide to the theory of NP-completeness. Freeman and Company, San Francisco (1979)

    MATH  Google Scholar 

  15. Golovach, P., Paulusma, D.: List coloring in the absence of two subgraphs. Discrete Appl. Math. 166, 123–130 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  16. Golovach, P., Paulusma, D., Song, J.: \(4\)-coloring \(H\)-free graphs when \(H\) is small. Discrete Appl. Math. 161, 140–150 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  17. Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718–780 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  18. Korobitsyn, D.: On the complexity of domination number determination in monogenic classes of graphs. Discrete Math. Appl. 2, 191–199 (1992)

    MathSciNet  Google Scholar 

  19. Korpelainen, N., Lozin, V., Malyshev, D., Tiskin, A.: Boundary properties of graphs for algorithmic graph problems. Theor. Comput. Sci. 412, 3544–3554 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  20. Korpelainen, N., Lozin, V., Razgon, I.: Boundary properties of well-quasi-ordered sets of graphs. Order 30, 723–735 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  21. Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in \(P_5\)-free graphs in polynomial time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 570–581 (2014)

  22. Lozin, V., Malyshev, D.: Vertex coloring of graphs with few obstructions. Discrete Appl. Math. (2015). doi:10.1016/j.dam.2015.02.015

  23. Lozin, V., Monnot, J., Ries, B.: On the maximum independent set problem in subclasses of subcubic graphs. J. Discrete Algorithms 31, 104–112 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  24. Lozin, V., Mosca, R.: Independent sets in extensions of \(2K_2\)-free graphs. Discrete Appl. Math. 146, 74–80 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  25. Lozin, V., Purcell, C.: Boundary properties of the satisfiability problems. Inf. Process. Lett. 113, 313–317 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  26. Lozin, V., Rautenbach, D.: On the band-, tree- and clique-width of graphs with bounded vertex degree. SIAM J. Discrete Math. 18, 195–206 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  27. Lozin, V., Zamaraev, V.: Boundary properties of factorial classes of graphs. J. Graph Theory 78, 207–218 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  28. Lozin, V.: Graph theory notes. https://homepages.warwick.ac.uk/~masgax/Graph-Theory-notes. Accessed 11 September 2015 (2015)

  29. Makino, M., Uno, Y., Ibaraki, T.: Minimum edge ranking spanning trees of threshold graphs. Lect. Notes Comput. Sci. 2518, 428–440 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  30. Malyshev, D.: Continued sets of boundary classes of graphs for colorability problems. Diskretnyi Analiz i Issledovanie Operatsii 16, 41–51 (2009). [in Russian]

    MathSciNet  MATH  Google Scholar 

  31. Malyshev, D.: On minimal hard classes of graphs. Diskretnyi Analiz i Issledovanie Operatsii 16, 43–51 (2009). [in Russian]

    MathSciNet  MATH  Google Scholar 

  32. Malyshev, D.: On the infinity of the set of boundary classes for the edge 3-colorability problem. J. Appl. Ind. Math. 4, 213–217 (2010)

    Article  MathSciNet  Google Scholar 

  33. Malyshev, D.: On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number. Discrete Math. Appl. 21, 645–649 (2011)

    Article  MATH  Google Scholar 

  34. Malyshev, D.: A study of the boundary graph classes for colorability problems. J. Appl. Ind. Math. 7, 221–228 (2013)

    Article  MathSciNet  Google Scholar 

  35. Malyshev, D.: Classes of subcubic planar graphs for which the independent set problem is polynomially solvable. J. Appl. Ind. Math. 7, 537–548 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  36. Malyshev, D.: Classes of graphs critical for the edge list-ranking problem. J. Appl. Ind. Math. 8, 245–255 (2014)

    Article  MathSciNet  Google Scholar 

  37. Malyshev, D.: The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices. Sib. Electron. Math. Rep. 11, 811–822 (2014)

    MATH  Google Scholar 

  38. Malyshev, D.: The coloring problem for classes with two small obstructions. Optim. Lett. 8, 2261–2270 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  39. Malyshev, D.: A complexity dichotomy and a new boundary class for the dominating set problem. J. Comb. Optim. (2015). doi:10.1007/s10878-015-9872-z

  40. Malyshev, D.: A complexity dichotomy for the dominating set problem. (2015). arXiv:1506.00202

  41. Malyshev, D.: The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs. Discrete Math. 338, 1860–1865 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  42. Malyshev, D.: Two cases of polynomial-time solvability for the coloring problem. J. Comb. Optim. (2015). doi:10.1007/s10878-014-9792-3

  43. Murphy, O.: Computing independent sets in graphs with large girth. Discrete Appl. Math. 35, 167–170 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  44. Papadimitriou, C., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1–11 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  45. De Ridder, N., et al.: Information system on graph classes and their inclusions. (2015). http://www.graphclasses.org. Accessed 21 June 2015

  46. Schweitzer, P.: Towards an isomorphism dichotomy for hereditary graph classes. (2014). arXiv:1411.1977

  47. Shen, A., Vereshchagin, N.: Basic set theory. Am. Math. Soc. 17, 1–130 (2002)

    MathSciNet  Google Scholar 

  48. Whitesides, S.: A method for solving certain graph recognition and optimization problems, with applications to perfect graphs. Ann. Discrete Math. 21, 281–297 (1984)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The research is partially supported by LATNA laboratory, National Research University Higher School of Economics, RF government Grant, ag. 11.G34.31.00357, and by Russian Foundation for Basic Research, Grant 14-01-00515-a, by the grant of President of Russian Federation MK-4819.2016.1.

Author information

Authors and Affiliations

  1. National Research University Higher School of Economics, 25/12 Bolshaja Pecherskaja Ulitsa, Nizhny Novgorod, 603155, Russia

    D. S. Malyshev

  2. University of Florida, 401 Weil Hall, P.O. Box 116595, Gainesville, FL, 326116595, USA

    P. M. Pardalos

Authors
  1. D. S. Malyshev
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. M. Pardalos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to D. S. Malyshev.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Malyshev, D.S., Pardalos, P.M. Critical hereditary graph classes: a survey. Optim Lett 10, 1593–1612 (2016). https://doi.org/10.1007/s11590-015-0985-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-015-0985-1

Keywords

Search

Navigation