Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2018, 12:2, 213-219
Volume 25, No 2, 2018, P. 5-18
UDC 519.178
V. E. Alekseev and S. V. Sorochan
New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
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.
Bibliogr. 12.
Keywords: independent set, forbidden subgraph, path, supergraph, polynomial time.
DOI: 10.17377/daio.2018.25.581
Vladimir E. Alekseev 1
Vladimir E. Alekseev 1
1. Lobachevskii Nizhniy Novgorod State University, IITMM,
23 Gagarin Ave., 603950 Nizhny Novgorod, Russia
e-mail: aleve@rambler.ru, svs-05@mail.ru
Received 8 June 2017
Revised 8 June 2017
References
[1] V. E. Alekseev, On the local restriction effect on the complexity of finding the graph independence number, in Kombinatorno-algebraicheskie metody v prikladnoi matematike (Combinatorial and algebraic methods in applied mathematics), pp. 3–13, Gorky: Izd. Gorkovskogo Univ., 1982.[2] V. E. Alekseev, On the number of maximal independent sets in graphs from hereditary classes, in Kombinatorno-algebraicheskie metody v diskretnoi optimizatsii (Combinatorial and algebraic methods in discrete optimization), pp. 5–8, Nizhny Novgorod: Izd. NNGU, 1991.
[3] V. E. Alekseev, A polynomial algorithm for finding the largest independent sets in claw-free graphs, Diskretn. Anal. Issled. Oper., Ser. 1, 6, No. 4, 3–19, 1999. Translated in Discrete Appl. Math., 135, No. 1–3, 3–16, 2004.
[4] V. E. Alekseev and D. V. Korobitsyn, Complexity of some problems for hereditary classes of graphs, Diskretn. Mat., 4, No. 4, 34–40, 1992.
[5] D. S. Malyshev and D. V. Sirotkin, Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs, Diskretn. Anal. Issled. Oper., 24, No. 3, 35–60, 2017. Translated in J. Appl. Ind. Math., 11, No. 3, 400–414, 2017.
[6] A. Grzesik, T. Klimošová, Mar. Pilipczuk, and Mic. Pilipczuk, Polynomial-time algorithm for Maximum Weight Independent Set on $P_6$-free graphs, 2017 (Cornell Univ. Libr. e-Print Archive, arXiv:1707.05491).
[7] W. Hsu, Y. Ikura, and G. L. Nemhauser, A polynomial algorithm for maximum weighted vertex packing in graphs without long odd cycles, Math. Program., 20, 225–232, 1981.
[8] T. Karthick and F. Maffray, Weighted independent sets in classes of $P_6$-free graphs, Discrete Appl. Math., 209, 217–226, 2016.
[9] D. Lokshtanov, M. Vatshelle, and Y. Villanger, Independent set in $P_5$-free graphs in polynomial time, in Proc. 25th Annu. ACM-SIAM Symp. Discrete Algorithms, Portland, OR, USA, Jan. 5–7, 2014, pp. 570–581, SIAM, Philadelphia, PA, 2014.
[10] V. V. Lozin, J. Monnot, and B. Ries, On the maximum independent set problem in subclasses of subcubic graphs, J. Discrete Algorithms, 31, 104–112, 2015.
[11] V. V. Lozin and R. Mosca, Independent sets in extension of $2K_2$-free graphs, Discrete Appl. Math., 146, No. 1, 74–80, 2005.
[12] V. V. Lozin and D. Rautenbach, Some results on graphs without long induced paths, Inf. Process. Lett., 88, 167–171, 2003.
