Комбинаторная надежность сетевых гиперграфов

В статье теория доминирования распространена на гиперграфы. Доказано, что 1) задача вычисления доминирования в классе $(s,t)$-гиперграфов ограниченной степени полиномиально разрешима; 2) доминирование циклических $(s,t)$-гиперграфов равно нулю, в то время как задача вычисления доминирования в классе нестандартных $r$-циклических $(s,t)$-гиперграфов является $\#P$-полной при любом фиксированном натуральном $r$. Выявлена гиперграфовая природа всех ранее полученных результатов о доминировании $d$-тривиальных графов, непосредственно вытекающих из перечисленных выше.
Конструктивно доказано существование псевдополиномиального (временна́я сложность которого полиномиальна относительно числа подгиперграфов) алгоритма решения проблемы вычисления комбинаторной надёжности (Rel-проблемы) в классе ациклических $(s,t)$-гиперграфов ограниченной степени. Для произвольного $(s,t)$-гиперграфа получена аддитивная формула символьного вычисления надёжности, длина которой равна числу ациклических подгиперграфов, а сложность вычисления каждого слагаемого определяется только сложностью вычисления доминирования локальных гиперграфов.
Доказана $\#P$-полнота задачи вычисления полинома комбинаторной надёжности в классе ациклических тривиальных $(s,t)$-гиперграфов степени 2, в которых число минимальных путей ограничено сверху линейной функцией от размерности этих $(s,t)$-гиперграфов. Это означает, в частности, что если P${}\ne{}$NP, то не существует квазиполиномиального алгоритма (временна́я сложность которого полиномиальна относительно числа минимальных подгиперграфов) решения Rel-проблемы в классе ациклических тривиальных $(s,t)$-гиперграфов степени 2.