Volume 19, No 4, 2012, P. 6672
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 polynomialtime solvability of the independent set problem is considered. We prove that if this problem is polynomialtime 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
email: dsmalyshev@rambler.ru
