×

Expanding operators for the independent set problem. (Russian, English) Zbl 1324.05143

Diskretn. Anal. Issled. Oper. 20, No. 2, 75-87 (2013); translation in J. Appl. Ind. Math. 7, No. 3, 412-419 (2013).
Summary: The notion is introduced of an expanding operator for the independent set problem. This notion is a useful tool for the constructive formation of new cases with the efficient solvability of this problem in the family of hereditary classes of graphs and is applied to hereditary parts of the set \(\text{Free}(\{P_5, C_5\})\). It is proved that if for a connected graph \(G\) the problem is polynomial-time solvable in the class \(\text{Free}(\{P_5, C_5, G\})\) then it remains so in the class \(\text{Free}(\{P_5, C_5, G\circ K_2, G\oplus K_{1,p}\})\) for every \(p\). We also find two new hereditary subsets of \(\text{Free}(\{P_5, C_5\})\) with polynomially solvable independent set problem that are not a corollary of applying the revealed operators.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI