Top

Journal of Applied and Industrial Mathematics

Published in:

01-03-2023

New Cases of Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Triodes

Author: S. V. Sorochan

Published in: Journal of Applied and Industrial Mathematics | Issue 1/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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 with \( k \) vertices is forbidden, then for \( k>5 \) the complexity of this problem is unknown. We consider intermediate cases where 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 with bounded vertex degrees are forbidden.

A triode and all its spanning supergraphs having large deficiency (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 graph has a vertex of bounded antidegree.

previous article Numerical Approach to Simulation of Geometry Variation during Sintering of Ceramics Based on the Finite Element Method

next article Decomposition of Symmetric Tensor Fields in

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

V. E. Alekseev and D. V. Korobitsyn, “On the complexity of some problems for hereditary classes of graphs,” Diskretn. Mat. 4 (4), 34–40 (1992) [in Russian].MathSciNetMATH

V. E. Alekseev and 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), 5–18 (2018) [J. Appl. Ind. Math. 12 (2), 213–219 (2018)].MathSciNetCrossRefMATH

V. E. Alekseev, “On the local restriction effect on the complexity of finding the graph independence number,” in Combinatorial-Algebraic Methods in Applied Mathematics (Izd. Gorkovsk. Univ., Gorky, 1982), 3–13 [in Russian].

V. E. Alekseev, “On the number of maximal independent sets in graphs from hereditary classes,” in Combinatorial-Algebraic Methods in Discrete Optimization (Izd. NNGU, Nizhny Novgorod, 1991), 5–8 [in Russian].

V. E. Alekseev, “A polynomial algorithm for finding the largest independent sets in claw-free graphs,” Diskretn. Anal. Issled. Oper. Ser. 1 6 (4), 3–19 (1999) [Discrete Appl. Math. 135 (1–3), 3–16 (2004)].MathSciNet

V. V. Lozin and R. Mosca, “Independent sets in extension of 2K2-free graphs,” Discrete Appl. Math. 146, 74–80 (2005).MathSciNetCrossRefMATH

D. Lokshantov, M. Vatshelle, and Y. Villanger, “Independent set in \( P_5 \)-free graphs in polynomial time,” Proc. Twenty-Fifth Annu. ACM–SIAM Symp. Discrete Algorithms, SODA 2014 (Portland, Oregon, USA, January 5–7, 2014), 570–581.

A. Grzesik, T. Klimosova, M. Pilipczuk, and M. Pilipczuk, “Polynomial-time algorithm for Maximum Weight Independent Set on \( P_6 \)-free graphs,” 2017. .

T. Karthick and F. Maffray, “Weighted independent sets in classes of \( P_6 \)-free graphs,” Discrete Appl. Math. 209, 217–226 (2016).MathSciNetCrossRefMATH

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).MathSciNetCrossRefMATH

11.

V. V. Lozin and D. Rautenbach, “Some results on graphs without long induced paths,” Inf. Process. Lett. 88, 167–171 (2003).MathSciNetCrossRefMATH

12.

D. Malyshev and D. Sirotkin, “Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs,” J. Appl. Ind. Math. 11 (3), 400–414 (2017).MathSciNetCrossRefMATH

13.

T. Abrishami, M. Chudnovsky, C. Dibek, and P. Rzaűewski, “Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws,” Proc. 2022 Annu. ACM–SIAM Symp. Discrete Algorithms (SODA) (2022), 1448–1470. https://epubs.siam.org/doi/epdf/10.1137/1.9781611977073.61 .

14.

V. Alekseev, V. V. Lozin, D. Malyshev, M. Milanic, “The maximum independent set problem in planar graphs,” Lect. Notes Comput. Sci. 5162 (4), 96–107 (2008).MathSciNetCrossRefMATH

15.

D. Malyshev, “Classes of subcubic planar graphs for which the independent set problem is polynomially solvable,” J. Appl. Ind. Math. Vol. 7 (4), 537–548 (2013).CrossRefMATH

16.

L. Lovász and M. D. Plummer, Matching Theory, vol. 29 of Ann. Discrete Math. (North-Holland, Amsterdam, 1986).

17.

G. Minty, “On maximal independent sets of vertices in claw-free graphs,” J. Combin. Theory. Ser. B 28 (3), 284–304 (1980).MathSciNetCrossRefMATH

18.

N. Sbihi, “Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile,” Discrete Math. 29 (1), 53–76 (1980).MathSciNetCrossRefMATH

19.

V. A. Emelichev et al., Graph Theory Lectures (Nauka, Moscow, 1990) [in Russian].

20.

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).CrossRefMATH

Title: New Cases of Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Triodes
Author: S. V. Sorochan
Publication date: 01-03-2023
Publisher: Pleiades Publishing
Published in: Journal of Applied and Industrial Mathematics / Issue 1/2023
Print ISSN: 1990-4789
Electronic ISSN: 1990-4797
DOI: https://doi.org/10.1134/S1990478923010210

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 1/2023

Numerical Simulation of Elastic Turbulence in a Bounded Two-Dimensional Cell

Mathematical Modeling of the Heavy Oil Production with Hydraulic Fracturing under Radio-Frequency Electromagnetic Irradiation

Parametric RANS Simulation of a Cavitation Flow in the Channel of a Control Valve Cage

Mathematical Modeling of Suspension Flow in the System of Intersecting Fractures

Modeling of a Single Bubble Dynamics at Boiling by Lattice Boltzmann Method

Adaptive Data Processing Algorithm in Problems of Measuring Three-Dimensional Geometry by Phase Triangulation Methods under Additive Noise in the Photodetector

Premium Partners