New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths |
| |
Authors: | V. E. Alekseev S. V. Sorochan |
| |
Affiliation: | 1.Institute of Information Technology, Mathematics and Mechanics,Lobachevskii Nizhny Novgorod State University,Nizhny Novgorod,Russia |
| |
Abstract: | The independent set problem is solvable in polynomial time for the graphs not containing the path P k for any fixed k. If the induced path P k is forbidden then the complexity of this problem is unknown for k > 6. We consider the intermediate cases that the induced path P k and some of its spanning supergraphs are forbidden. We prove the solvability of the independent set problem in polynomial time for the following cases: (1) the supergraphs whose minimal degree is less than k/2 are forbidden; (2) the supergraphs whose complementary graph has more than k/2 edges are forbidden; (3) the supergraphs from which we can obtain P k by means of graph intersection are forbidden. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |