An inference algorithm for monotone Boolean functions associated with undirected graphs

Существует достаточно прикладных задач, в которых одним из инструментов моделирования служат булевы функции, среди которых важную роль играют монотонные булевы функции. Например, монотонные булевы функции являются удобным средством для описания структуры совместных подсистем несовместных систем условий, поскольку совместность является монотонным свойством.
В работе рассматриваются монотонные булевы функции, порождаемые неориентированными графами, в которых нули функции определяются как такие двоичные наборы, для которых соответствующий подграф исходного неориентированного графа пуст, или не содержит ребер. Для такого класса монотонных булевых функций даются постановки задач, связанных с выделением верхних нулей и максимальных верхних нулей функции. Вводятся понятия $k$-вершины и $(k, m)$-вершины в неориентированном графе. Показано, что для любой $k$-вершины исходного графа существует максимальный верхний нуль порожденной монотонной булевой функции, в котором компонента $x_{i}$, соответствующая этой $k$-вершине, принимает значение $1$.
На основе этого утверждения построен алгоритм выделения максимального верхнего нуля для рассматриваемого класса монотонных булевых функций, который гарантирует, при определенных условиях, нахождение точного решения задачи поиска максимального верхнего нуля, либо приводит к снижению размерности исходной задачи. Предложенный алгоритм обобщается для случая использования $(k, m)$-вершин. Построенный алгоритм выделяет верхний нуль монотонной булевой функции и дает оценку его отклонения от максимального верхнего нуля по числу единиц в этих наборах. Алгоритм имеет сложность $O(n^2p)$, где $n$ — число вершин и $p$ — число ребер исходного графа.