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/

[1] V. E. Alekseev, “On the local restriction effect on the complexity of finding the graph independence number”, Combinatorial and algebraic methods in applied mathematics, Izd. Gorkovskogo Univ., Gorky, 1982, 3–13

[2] V. E. Alekseev, “On the number of maximal independent sets in graphs from hereditary classes”, Combinatorial and algebraic methods in discrete optimization, Izd. NNGU, Nizhny Novgorod, 1991, 5–8

[3] V. E. Alekseev, “A polynomial algorithm for finding the largest independent sets in claw-free graphs”, Discrete Appl. Math., 135:1–3 (2004), 3–16 | MR | MR | Zbl

[4] V. E. Alekseev, D. V. Korobitsyn, “Complexity of some problems for hereditary classes of graphs”, Diskretn. Mat., 4:4 (1992), 34–40 | MR | Zbl

[5] D. S. Malyshev, D. V. Sirotkin, “Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs”, J. Appl. Ind. Math., 11:3 (2017), 400–414 | DOI | DOI | MR | Zbl

[6] Grzesik A., Klimošová T., Pilipczuk Mar., Pilipczuk Mic., Polynomial-time algorithm for maximum weight independent set on $P_6$-free graphs, 2017, arXiv: 1707.05491

[7] Hsu W., Ikura Y., Nemhauser G. L., “A polynomial algorithm for maximum weighted vertex packing in graphs without long odd cycles”, Math. Program., 20 (1981), 225–232 | DOI | MR | Zbl

[8] Karthick T., Maffray F., “Weighted independent sets in classes of $P_6$-free graphs”, Discrete Appl. Math., 209 (2016), 217–226 | DOI | MR | Zbl

[9] Lokshtanov D., Vatshelle M., Villanger Y., “Independent set in $P_5$-free graphs in polynomial time”, Proc. 25th Annu. ACM-SIAM Symp. Discrete Algorithms, SODA 2014 (Portland, Oregon, USA, Jan. 5–7, 2014), SIAM, Philadelphia, PA, 2014, 570–581 | MR

[10] Lozin V. V., Monnot J., Ries B., “On the maximum independent set problem in subclasses of subcubic graphs”, J. Discrete Algorithms, 31 (2015), 104–112 | DOI | MR | Zbl

[11] Lozin V. V., Mosca R., “Independent sets in extension of $2K_2$-free graphs”, Discrete Appl. Math., 146 (2005), 74–80 | DOI | MR | Zbl

[12] Lozin V. V., Rautenbach D., “Some results on graphs without long induced paths”, Inf. Process. Lett., 88 (2003), 167–171 | DOI | MR | Zbl