Geodesic
Critical elements in combinatorially closed families of graph classes
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 1, pp. 81-96.

Voir la notice de l'article provenant de la source Math-Net.Ru

The notions of boundary and minimal hard classes of graphs, united by the term “critical classes”, are useful tools for analysis of computational complexity of graph problems in the family of hereditary graph classes. In this family, boundary classes are known for several graph problems. In the paper, we consider critical graph classes in the families of strongly hereditary and minor closed graph classes. Prior to our study, there was the only one example of a graph problem for which boundary classes were completely described in the family of strongly hereditary classes. Moreover, no boundary classes were known for any graph problem in the family of minor closed classes. In this article, we present several complete descriptions of boundary classes for these two families and some classical graph problems. For the problem of $2$-additive approximation of graph bandwidth, we find a boundary class in the family of minor closed classes. Critical classes are not known for this problem in the other two families of graph classes. Bibliogr. 21.
Keywords: computational complexity, hereditary class, critical class
Mots-clés : efficient algorithm. 
@article{DA_2017_24_1_a4,
     author = {D. S. Malyshev},
     title = {Critical elements in combinatorially closed families of graph classes},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {81--96},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_1_a4/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Critical elements in combinatorially closed families of graph classes
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 81
EP  - 96
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_1_a4/
LA  - ru
ID  - DA_2017_24_1_a4
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Critical elements in combinatorially closed families of graph classes
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 81-96
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_1_a4/
%G ru
%F DA_2017_24_1_a4
D. S. Malyshev. Critical elements in combinatorially closed families of graph classes. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 1, pp. 81-96. http://geodesic.mathdoc.fr/item/DA_2017_24_1_a4/

[1] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | Zbl

[2] D. S. Malyshev, “Continuum sets of boundary graph classes for the colorability problems”, Diskretn. Anal. Issled. Oper., 16:5 (2009), 41–51 (Russian) | Zbl

[3] D. S. Malyshev, “On minimal hard classes of graphs”, Diskretn. Anal. Issled. Oper., 16:6 (2009), 43–51 (Russian)

[4] D. S. Malyshev, “Classes of graphs critical for the edge list-ranking problem”, J. Appl. Ind. Math., 8:2 (2014), 245–255 | DOI | MR | Zbl

[5] Alekseev V. E., “On easy and hard hereditary classes of graphs with respect to the independent set problem”, Discrete Appl. Math., 132:1–3 (2003), 17–26 | DOI | MR | Zbl

[6] Alekseev V. E., Boliac R., Korobitsyn D. V., Lozin V. V., “NP-hard graph problems and boundary classes of graphs”, Theor. Comput. Sci., 389:1–2 (2007), 219–236 | DOI | MR | Zbl

[7] Alekseev V. E., Korobitsyn D. V., Lozin V. V., “Boundary classes of graphs for the dominating set problem”, Discrete Math., 285:1–3 (2004), 1–6 | DOI | MR | Zbl

[8] Arnborg S., Proskurowski A., “Linear time algorithms for NP-hard problems restricted to partial $k$-trees”, Discrete Appl. Math., 23:1 (1989), 11–24 | DOI | MR | Zbl

[9] Bodlaender H. L., “Dynamic programming on graphs with bounded treewidth”, Automata, Languages and Programming, Proc. 15th Int. Colloq. (Tampere, Finland, July 11–15, 1988), Lect. Notes Comput. Sci., 317, Springer-Verl., Heidelberg, 1988, 105–118 | DOI | MR

[10] Bodlaender H. L., “A partial $k$-arboretum of graphs with bounded treewidth”, Theor. Comput. Sci., 209:1–2 (1998), 1–45 | DOI | MR | Zbl

[11] Boliac R., Lozin V. V., “On the clique-width of graphs in hereditary classes”, Algorithms and Computation, Proc. 13th Int. Symp. (Vancouver, Canada, Nov. 21–23, 2002), Lect. Notes Comput. Sci., 2518, Springer, Heidelberg, 2002, 44–54 | DOI | MR | Zbl

[12] Courcelle B., Makowsky J., Rotics U., “Linear time solvable optimization problems on graphs of bounded clique-width”, Theory Comput. Syst., 33:2 (2000), 125–150 | DOI | MR | Zbl

[13] Dubey C., Feige U., Unger W., “Hardness results for approximating the bandwidth”, J. Comput. Syst. Sci., 77:1 (2011), 62–90 | DOI | MR | Zbl

[14] Fellows M., Lokshtanov D., Misra N., Rosamond F., Saurabh S., “Graph layout problems parameterized by vertex cover”, Algorithms and Computation, Proc. 19th Int. Symp. (Gold Coast, Australia, Dec. 15–17, 2008), Lect. Notes Comput. Sci., 5369, Springer, Heidelberg, 2008, 294–305 | DOI | MR | Zbl

[15] Gurski F., Wanke E., “Line graphs of bounded clique-width”, Discrete Math., 307:22 (2007), 2734–2754 | DOI | MR | Zbl

[16] Kobler D., Rotics D., “Edge dominating set and colorings on graphs with fixed clique-width”, Discrete Appl. Math., 126:2–3 (2003), 197–221 | DOI | MR | Zbl

[17] Miller Z., “The bandwidth of caterpillar graphs”, Congr. Numerantium, 33 (1981), 235–252 | MR | Zbl

[18] Muradian D., “The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete”, Theor. Comput. Sci., 307:3 (2003), 567–572 | DOI | MR | Zbl

[19] Robertson N., Seymour P., “Graph minors. V: Excluding a planar graph”, J. Comb. Theory, Ser. B, 41:1 (1986), 92–114 | DOI | MR | Zbl

[20] Robertson N., Seymour P., “Graph minors. XX: Wagner's conjecture”, J. Comb. Theory, Ser. B, 92:2 (2004), 325–357 | DOI | MR | Zbl

[21] Saxe J. B., “Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time”, SIAM J. Algebraic Discrete Methods, 1:4 (1980), 363–369 | DOI | MR | Zbl