Geodesic
New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 2, pp. 5-18

Voir la notice de l'article provenant de la source Math-Net.Ru

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. Bibliogr. 12.
Keywords: independent set, forbidden subgraph, path, supergraph
Mots-clés : polynomial time. 
@article{DA_2018_25_2_a0,
     author = {V. E. Alekseev and S. V. Sorochan},
     title = {New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--18},
     publisher = {mathdoc},
     volume = {25},
     number = {2},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2018_25_2_a0/}
}
TY  - JOUR
AU  - V. E. Alekseev
AU  - S. V. Sorochan
TI  - New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2018
SP  - 5
EP  - 18
VL  - 25
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2018_25_2_a0/
LA  - ru
ID  - DA_2018_25_2_a0
ER  - 
%0 Journal Article
%A V. E. Alekseev
%A S. V. Sorochan
%T New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
%J Diskretnyj analiz i issledovanie operacij
%D 2018
%P 5-18
%V 25
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2018_25_2_a0/
%G ru
%F DA_2018_25_2_a0
V. E. Alekseev; S. V. Sorochan. New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 2, pp. 5-18. http://geodesic.mathdoc.fr/item/DA_2018_25_2_a0/