Diskretnyi Analiz i Issledovanie Operatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


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




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Diskretnyi Analiz i Issledovanie Operatsii, 2023, Volume 30, Issue 1, Pages 85–109
DOI: https://doi.org/10.33048/daio.2023.30.752 (Mi da1317) 		 
New cases of polynomial solvability of the independent set problem for graphs with forbidden triods

S. V. Sorochan

Lobachevsky Nizhny Novgorod State University, 23 Gagarin Avenue, 603950 Nizhny Novgorod, Russia
Full-text PDF (403 kB)
References:
PDF
HTML
DOI: https://doi.org/10.33048/daio.2023.30.752
Abstract: A triode is a tree with three leaves and a single vertex of degree $3$. The independent set problem is solvable in polynomial time for graphs that do not contain a triode as a subgraph with any fixed number of vertices. If the induced triode having $k$ vertices is forbidden, then for $k>5$ the complexity of this problem is unknown. We consider intermediate cases when an induced triode with any fixed number of vertices and some of its spanning supergraphs are forbidden. For an arbitrary triode with a fixed vertex number, we prove the solvability of the independent set problem in polynomial time in the following cases:
  • a triode and all its spanning supergraphs having bounded vertex degrees are forbidden;
  • a triode and all its spanning supergraphs having large deficit (the number of edges in the complementary graph) are forbidden;
  • a triode and all its supergraphs from which this triode can be obtained using the graph intersection operation are forbidden, provided the fraph has a vertex with bounded anti-degree.

Bibliogr. 20.
Keywords: independent set, IS-easy class, IS-hard class, monotonic class, hereditary class, forbidden subgraph, triode, supergraph, polynomial algorithm.
Funding agency
The author is grateful to the referee for valuable comments regarding the review of sources related to the research topic.
Received: 31.08.2022
Revised: 03.11.2022
Accepted: 03.11.2022
English version:
Journal of Applied and Industrial Mathematics, 2023, Volume 17, Issue 1, Pages 185–198
DOI: https://doi.org/10.1134/S1990478923010210
Bibliographic databases:
Document Type: Article
UDC: 519.178
Language: Russian
Citation: S. V. Sorochan, “New cases of polynomial solvability of the independent set problem for graphs with forbidden triods”, Diskretn. Anal. Issled. Oper., 30:1 (2023), 85–109; J. Appl. Industr. Math., 17:1 (2023), 185–198
Citation in format AMSBIB
\Bibitem{Sor23}
\by S.~V.~Sorochan
\paper New cases of polynomial solvability of~the~independent set problem for~graphs~with~forbidden~triods
\jour Diskretn. Anal. Issled. Oper.
\yr 2023
\vol 30
\issue 1
\pages 85--109
\mathnet{http://mi.mathnet.ru/da1317}
\mathscinet{https://mathscinet.ams.org/mathscinet-getitem?mr=4569859}
\transl
\jour J. Appl. Industr. Math.
\yr 2023
\vol 17
\issue 1
\pages 185--198
\crossref{https://doi.org/10.1134/S1990478923010210}
Linking options:
  • https://www.mathnet.ru/eng/da1317
  • https://www.mathnet.ru/eng/da/v30/i1/p85
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025