Geodesic
New cases of polynomial solvability of~the~independent set problem for~graphs~with~forbidden~triods
Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 1, pp. 85-109

Voir la notice de l'article provenant de la source Math-Net.Ru

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, supergraph
Mots-clés : triode, polynomial algorithm. 
@article{DA_2023_30_1_a4,
     author = {S. V. Sorochan},
     title = {New cases of polynomial solvability of~the~independent set problem for~graphs~with~forbidden~triods},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {85--109},
     publisher = {mathdoc},
     volume = {30},
     number = {1},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2023_30_1_a4/}
}
TY  - JOUR
AU  - S. V. Sorochan
TI  - New cases of polynomial solvability of~the~independent set problem for~graphs~with~forbidden~triods
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2023
SP  - 85
EP  - 109
VL  - 30
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2023_30_1_a4/
LA  - ru
ID  - DA_2023_30_1_a4
ER  - 
%0 Journal Article
%A S. V. Sorochan
%T New cases of polynomial solvability of~the~independent set problem for~graphs~with~forbidden~triods
%J Diskretnyj analiz i issledovanie operacij
%D 2023
%P 85-109
%V 30
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2023_30_1_a4/
%G ru
%F DA_2023_30_1_a4
S. V. Sorochan. New cases of polynomial solvability of~the~independent set problem for~graphs~with~forbidden~triods. Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 1, pp. 85-109. http://geodesic.mathdoc.fr/item/DA_2023_30_1_a4/