Extending operators for the independent set problem

D. S. Malyshev

Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 2, pp. 75-87.

Résumé

The notion of an extending operator for the independent set problem is introduced. This notion is a useful tool for constructive obtaining of new cases with the effective solvability of this problem in the family of hereditary classes of graphs and is applied to hereditary parts of the set $Free(\{P_5,C_5\})$. It is proved that if for a connected graph $G$ the problem is polynomial-time solvable in the class $Free(\{P_5,C_5,G\})$, then it remains the same in the class $Free(\{P_5,C_5,G\circ\overline K_2,G\oplus K_{1,p}\})$ for any $p$. New hereditary subsets of $Free(\{P_5,C_5\})$ with the independent set problem solvable in polynomial time that are not results of application of the specified operators are found. Bibliogr. 22.

Détail

Keywords: independent set problem, theory of computational complexity, extending operator, effective algorithm.

Bibliographie

[1] Alekseev V. E., Talanov V. A., Grafy i algoritmy. Struktury dannykh. Modeli vychislenii, Internet-Universitet Informatsionnykh Tekhnologii, M.; BINOM. Laboratoriya znanii, M., 2006, 320 pp.

[2] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Nauka, M., 1990, 384 pp. | MR | Zbl

[3] Zykov A. A., Osnovy teorii grafov, Nauka, M., 1987, 383 pp. | MR | Zbl

[4] Malyshev D. S., “Polinomialnaya razreshimost zadachi o nezavisimom mnozhestve v klasse grafov bez porozhdënnykh prostykh puti i tsikla s pyatyu vershinami i bolshoi kliki”, Diskret. analiz i issled. operatsii, 19:3 (2012), 58–64 | MR

[5] Malyshev D. S., “Polinomialnaya razreshimost zadachi o nezavisimom mnozhestve dlya odnogo klassa grafov malogo diametra”, Diskret. analiz i issled. operatsii, 19:6 (2012), 37–48

[6] Kharari F., Teoriya grafov, Mir, M., 1982, 301 pp.

[7] 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 | MR

[8] Arbib C., Mosca R., “On ($P_5$, diamond)-free graphs”, Discrete Math., 250 (2002), 1–22 | MR | Zbl

[9] Brandstadt A., Mosca R., “On the structure and stability number of $P_5$- and co-chair-free graphs”, Discrete Appl. Math., 132 (2003), 47–65 | MR

[10] Brandstadt A., Le H.-O., Mosca R., “Chordal co-gem-free and $(P_5, gem)$-free graphs have bounded clique-width”, Discrete Appl. Math., 145:2 (2005), 232 | MR

[11] Bondy A., Murty U., Graph theory, Grad. Texts Math., 244, Springer-Verl., Heidelberg, 2008, 654 pp. | MR | Zbl

[12] Chudnovsky M., Robertson N., Seymour P., Thomas R., “The strong perfect graph theorem”, Ann. Math., 164 (2002), 51–229 | MR

[13] Diestel R., Graph theory, Grad. Texts Math., 173, Springer-Verl., Heidelberg, 2010, 451 pp. | MR | Zbl

[14] Gerber M., Lozin V., “On the stable set problem in special $P_5$-free graphs”, Discrete Appl. Math., 125 (2003), 215–224 | MR | Zbl

[15] Grötschel M., Lovász L., Schrijver A., Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, 2, Springer-Verl., Berlin, 1993, 362 pp. | MR

[16] Lovasz L., “A characterization of perfect graphs”, J. Comb. Theory Ser. B, 13 (1972), 95–98 | MR | Zbl

[17] Lozin V., Mosca R., “Maximum independent sets in subclasses of $P_5$-free graphs”, Inf. Process. Lett., 109:6 (2009), 319–324 | MR | Zbl

[18] Mosca R., “Polynomial algorithms for the maximum stable set problem on particular classes of $P_5$-free graphs”, Inf. Process. Lett., 61:3 (1997), 137–143 | MR

[19] Mosca R., “Stable sets in certain $P_6$-free graphs”, Discrete Appl. Math., 92 (1999), 177–191 | MR | Zbl

[20] Mosca R., “Some results on maximum stable sets in certain $P_5$-free graphs”, Discrete Appl. Math., 132 (2003), 175–183 | MR | Zbl

[21] Mosca R., “Some observations on maximum weight stable sets in certain $P_5$-free graph”, Eur. J. Oper. Res., 184:3 (2008), 849–859 | MR | Zbl

[22] Simone C. D., Mosca R., “Stable set and clique polytopes of $(P_5, gem)$-free graphs”, Discrete Math., 307:22 (2007), 2661–2670 | MR | Zbl