Том 14, серия 1, номер 2, 2007 г., Стр. 68-94

УДК 519.1
А. А. Черняк, С. В. Суздаль
Комбинаторная надёжность сетевых гиперграфов

Аннотация:
В статье теория доминирования распространена на гиперграфы. Доказано, что 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.
Библ. 32.

Черняк А. А. ¹
Суздаль С. В. ²
1.  Белорусский государственный педагогический университет им. М. Танка, кафедра математики физического факультета,
ул. Советская, 18, 220050 Минск, Республика Беларусь
2. Белорусский государственный университет, Механико–математический факультет,
пр. Независимости, 4, 220030 Минск, Республика Беларусь
е-mail: arkcharniak@tut.by, suzdal@bsu.by

Статья поступила 14 апреля 2005 г.
Исправленный вариант — 15 декабря 2006 г.