Том 19, номер 4, 2012 г., Стр. 66-72

УДК 519.178
Малышев  Д. С.
Полиномиальная разрешимость задачи о независимом множестве для одного класса графов малого диаметра

Аннотация:
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов ${\mathcal Free}(\{P_5,C_5\})$. Именно, доказывается, что если эта задача полиномиально разрешима в классе ${\mathcal Free}(\{P_5,C_5,G\})$, то для любого графа $H$, который может быть индуктивно получен из $G$ применением к текущему графу сложения с $K_1$ или умножения на $K_1$, эта задача имеет тот же вычислительный статус в классе ${\mathcal Free}(\{P_5,C_5,H\})$.
Библиогр. 10.

Ключевые слова: задача о независимом множестве, вычислительная сложность, эффективный алгоритм.

Малышев Дмитрий Сергеевич ^1,2
1. Нац. исслед. университет Высшая школа экономики в Ниж. Новгороде,
ул. Б. Печёрская, 25/12, 603155 Н. Новгород, Россия
2. Нижегородский гос. университет им. Н. И. Лобачевского,
пр-т Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия
е-mail: dsmalyshev@rambler.ru

Статья поступила 19 октября 2011 г.

Литература

[1] Arbib C., Mosca R. On ($P_5$, diamond)-free graphs // Discrete Math. — 2002. — Vol. 250. — P. 1–22.

[2] Brandstadt A., Mosca R. On the structure and stability number of $P_5$- and co-chair-free graphs // Discrete Appl. Math. — 2003. — Vol. 132. — P. 47–65.

[3] Brandstadt A., Le H.-O., Mosca R. Chordal co-gem-free and ($P_5$, gem)-free graphs have bounded clique-width // Discrete Appl. Math. — 2005. — Vol. 145, N 2. — P. 232.

[4] Lozin V., Mosca R. Maximum independent sets in subclasses of $P_5$-free graphs // Inf. Process. Lett. — 2009. — Vol. 109, N 6. — P. 319–324.

[5] Minty G. On maximal independent sets of vertices in claw-free graphs // J. Comb. Theory, Ser. B. — 1980. — Vol. 28. — P. 284–304.

[6] Mosca R. Polynomial algorithms for the maximum stable set problem on particular classes of $P_5$-free graphs // Inf. Process. Lett. — 1997. — Vol. 61, N 3. — P. 137–143.

[7] Mosca R. Some results on maximum stable sets in certain $P_5$-free graphs // Discrete Appl. Math. — 2003. — Vol. 132. — P. 175–183.

[8] Mosca R. Some observations on maximum weight stable sets in certain $P$ // Eur. J. Oper. Res. — 2008. — Vol. 184, N 3. — P. 849–859.

[9] Murphy O. Computing independent sets in graphs with large girth // Discrete Appl. Math. — 1992. — Vol. 35. — P. 167–170.

[10] Simone C. D., Mosca R. Stable set and clique polytopes of ($P_5$, gem)-free graphs // Discrete Math. — 2007. — Vol. 307, N 22. — P. 2661–2670.