Volume 19, No 4, 2012, P. 66-72

UDC 519.178
D. S. Malyshev 
Polynomial solvability of the independent set problem for one class of graphs with small diameter

Abstract:
A constructive approach to forming new cases in the family of hereditary parts of the set ${\mathcal Free}(\{P_5,C_5\})$ with polynomial-time solvability of the independent set problem is considered. We prove that if this problem is polynomial-time solvable in the class ${\mathcal Free}(\{P_5,C_5,G\})$ then for any graph $H$ which can inductively be obtained from $G$ by means of applying addition with $K_1$ or multiplication by $K_1$ to the graph $G$ the problem has the same computational status in ${\mathcal Free}(\{P_5,C_5,H\})$.
Bibliogr. 10.

Keywords: the independent set problem, computational complexity, polynomial algorithm.

Malyshev Dmitrii Sergeevich ^1,2
1. Nizhniy Novgorod Higher School of Economics,
25/12 B. Pecherskaya str., 603155 Nizhny Novgorod, Russia
2. Nizhniy Novgorod State University,
23 Gagarina ave., 603950 Nizhniy Novgorod, Russia
e-mail: dsmalyshev@rambler.ru