Ациклические монотонные графы: доминирование и надежность

Abstract

The problem of computing domination is proved to be NP-hard even restricted to acyclic monotone graphs with the number of cutsets (pathsets) quadratically depending on the graph dimension. The similar problem for acyclic monotone graphs of the fixed degree is shown to be polynomially solvable. It is also proved that the problem of computing reliability is NP-hard even restricted to the class of dc-trivial monotone graph of degree 2 in which the number of cutsets (pathsets) linearly depends on the graph dimension.