Расщепляемые графы в задачах покрытия

Abstract

The # P-completeness of reliability covering problem (RCP) is proved in the class of split graphs that are trees. Boundary conditions for a set of routes that give a criterion for polynomial solvability of the RCP are found for arbitrary trees. As a corollary, the subclass of trees with a set of routes being split graphs, in which the RCP is polynomially solvable, is characterized. The split dimension of trees is shown to be determined in linear time.