RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskretn. Anal. Issled. Oper.: Year: Volume: Issue: Page: Find

 Diskretn. Anal. Issled. Oper., 2018, Volume 25, Issue 2, Pages 5–18 (Mi da893)

New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths

V. E. Alekseev, S. V. Sorochan

Lobachevskii Nizhniy Novgorod State University, IITMM, 23 Gagarin Ave., 603950 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. Bibliogr. 12.

Keywords: independent set, forbidden subgraph, path, supergraph, polynomial time.

 Funding Agency Grant Number Russian Foundation for Basic Research 17-01-00710a

DOI: https://doi.org/10.17377/daio.2018.25.581

Full text: PDF file (328 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2018, 12:2, 213–219

UDC: 519.178
Revised: 22.11.2017

Citation: V. E. Alekseev, S. V. Sorochan, “New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths”, Diskretn. Anal. Issled. Oper., 25:2 (2018), 5–18; J. Appl. Industr. Math., 12:2 (2018), 213–219

Citation in format AMSBIB
\Bibitem{AleSor18} \by V.~E.~Alekseev, S.~V.~Sorochan \paper New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths \jour Diskretn. Anal. Issled. Oper. \yr 2018 \vol 25 \issue 2 \pages 5--18 \mathnet{http://mi.mathnet.ru/da893} \crossref{https://doi.org/10.17377/daio.2018.25.581} \elib{https://elibrary.ru/item.asp?id=32729776} \transl \jour J. Appl. Industr. Math. \yr 2018 \vol 12 \issue 2 \pages 213--219 \crossref{https://doi.org/10.1134/S1990478918020023} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85047800693}