Loading [MathJax]/jax/output/SVG/config.js
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
References:
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.
Received: 31.08.2022
Revised: 03.11.2022
Accepted: 03.11.2022
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
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}
\crossref{https://doi.org/10.33048/daio.2023.30.752}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4569859}
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
    Дискретный анализ и исследование операций
    Statistics & downloads:
    Abstract page:112
    Full-text PDF :9
    References:20
    First page:5
     
      Contact us:
    math-net2025_01@mi-ras.ru
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025