Geodesic
Critical graph classes for the edge list-ranking problem
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 6, pp. 59-76.

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

The edge list-ranking problem is a model for some parallel processes. We study the computational complexity of this problem for graph sets closed under isomorphism and deletion of vertices (hereditary classes). We describe all finitely defined and minor-closed cases for which the problem is polynomial-time solvable. We find the whole set of “critical” graph classes, the inclusion of which in a finitely defined class is equivalent to intractability of the edge list-ranking problem in this class. It seems to be the first result on a complete description for non-artificial NP-complete graph problems. For this problem, we constructively prove that among minimal under inclusion NP-complete hereditary cases there are exactly 5 finitely defined classes and exactly 1 minor-closed class. Ill. 1, bibliogr. 13.
Keywords: computational complexity, hereditary class, boundary class, minimal hard class, edge list-ranking problem.
Mots-clés : polynomial algorithm 
@article{DA_2013_20_6_a4,
     author = {D. S. Malyshev},
     title = {Critical graph classes for the edge list-ranking problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {59--76},
     publisher = {mathdoc},
     volume = {20},
     number = {6},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_6_a4/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Critical graph classes for the edge list-ranking problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 59
EP  - 76
VL  - 20
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_6_a4/
LA  - ru
ID  - DA_2013_20_6_a4
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Critical graph classes for the edge list-ranking problem
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 59-76
%V 20
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_6_a4/
%G ru
%F DA_2013_20_6_a4
D. S. Malyshev. Critical graph classes for the edge list-ranking problem. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 6, pp. 59-76. http://geodesic.mathdoc.fr/item/DA_2013_20_6_a4/

[1] Malyshev D. S., “O minimalnykh slozhnykh elementakh reshetki nasledstvennykh klassov grafov”, Mat. VII molodezh. nauch. shkoly po diskret. matematike i eë pril., Izd-vo IPM RAN, M., 2009, 12–17

[2] Malyshev D. S., “O minimalnykh slozhnykh klassakh grafov”, Diskret. analiz i issled. operatsii, 16:6 (2009), 43–51 | MR | Zbl

[3] Malyshev D. S., Issledovanie granits effektivnoi razreshimosti v semeistve nasledstvennykh klassov grafov, Diss. $\dots$ kand. fiz.–mat. nauk: 01.01.09, Nizhnii Novgorod, 2009, 113 pp.

[4] Malyshev D. S., “Posledovatelnye minimumy reshëtki nasledstvennykh klassov grafov dlya zadachi o rëbernom spiskovom ranzhirovanii”, Vestn. Nizhegorodsk. un-ta im. N. I. Lobachevskogo, 2010, no. 4, 133–136 | MR

[5] Malyshev D. S., “Minimalnye slozhnye klassy dlya zadachi o rëbernom spiskovom ranzhirovanii”, Diskret. analiz i issled. operatsii, 18:1 (2011), 70–76 | MR | Zbl

[6] Malyshev D. S., Alekseev V. E., “Granichnye klassy dlya zadach o spiskovom ranzhirovanii otnositelno lesov”, Diskret. analiz i issled. operatsii, 18:6 (2011), 61–70 | MR | Zbl

[7] Malyshev D. S., “Analiz slozhnosti zadachi o rëbernom spiskovom ranzhirovanii dlya nasledstvennykh klassov grafov s ne bolee chem tremya zapretami”, Diskret. analiz i issled. operatsii, 19:1 (2012), 74–96 | MR

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

[9] Dereniowski D., “Edge ranking of weighted trees”, Discrete Appl. Math., 154 (2006), 1198–1209 | DOI | MR | Zbl

[10] Dereniowski D., “The complexity of list ranking of trees”, Ars Comb., 86 (2008), 97–114 | MR | Zbl

[11] Leiserson C., “Area-efficient graph layout (for VLSI)”, Proc. 21st Ann. IEEE Symp. Foundations of Computer Science, IEEE, Syracuse, 1980, 270–281

[12] Liu J., “The role of elimination trees in sparse factorization”, SIAM J. Matrix Anal. Appl., 11 (1990), 134–172 | DOI | MR | Zbl

[13] Makino K., Uno Y., Ibaraki T., “Minimum edge ranking spanning trees of threshold graphs”, Lect. Notes Comput. Sci., 2518, 2002, 428–440 | DOI | MR | Zbl