Алгоритм покрытия краевой клики

Я работал над аналогичной проблемой 2 года назад и никогда не видел никаких стандартных существующих подходов к ней. Я сделал следующее:

1. Вычислите все максимальные клики. В моем случае MACE оказался намного лучше, чем Bron-Kerbosch.
2. Создайте задачу удовлетворения ограничений для определения минимального количества кликов, необходимых для покрытия графа. Вы можете использовать SAT, Minizinc, инструменты MIP для этого. Какой выбрать? Это зависит от ваших навыков, временных ресурсов, окружения и десятков других параметров. Если мы говорим о проверке концепции, я бы остановился на Minizinc.

Немного подробностей для второй части. Определите набор логических переменных для каждого ребра, если оно равно value == True, то оно покрыто, иначе — нет. Добавьте ограничения, позволяющие покрывать наборы ребер только относительно каждой клики. Наконец, добавьте переменные, соответствующие каждой клике, если это == True, то это уже используется, иначе это не так. Наконец, требуется, чтобы все ребра были покрыты И количество используемых клик было минимальным.

Я бы собирал максимальные клики, как вы делаете сейчас (или, возможно, используя другой алгоритм, как предложено CaptainTrunky), но затем используйте ветвь и граница. Это не гарантирует ускорение, но часто приводит к значительному ускорению на «простых» экземплярах.

Особенно:

• Instead of trying all subsets of maximal cliques in increasing subset size order, pick an edge uv and branch on it. This means:
  • For each maximal clique C containing uv:
    • Make a tentative new partial solution that contains all cliques in the current solution
    • Добавьте C к этому частичному решению
    • Создайте новую подзадачу, содержащую текущий граф подзадачи, но со всеми вершинами в C, свернутыми в одну вершину.
    • Recurse для решения этой меньшей подзадачи.
• Следите за лучшим полным решением на данный момент. Это ваша верхняя граница (UB). Вам не нужно продолжать обработку какой-либо подзадачи, которая уже достигла этой верхней границы, но все еще имеет ребра; лучшее решение уже существует!
• Лучше всего выбрать ребро для ветвления, которое покрыто как можно меньшим числом клик. Выбирая в каком порядке пробовать эти клики, сначала попробуйте тот, который, по вашему мнению, будет лучшим (возможно, самым большим).

А вот идея для нижней границы для улучшения уровня обрезки:

Если подграф G' содержит независимый набор размера s, вам понадобится не менее s клик для покрытия G' (поскольку никакая клика не может покрывать две или более вершин в независимом множестве). Вычисление максимально возможного IS является NP-сложным и, следовательно, непрактичным здесь, но вы можете получить дешевую оценку, используя 2-аппроксимацию для Vertex Cover: просто продолжайте выбирать ребро и отбрасывать обе вершины, пока ребер не останется; если вы отбросили k ребер, то останется ИС, находящаяся в пределах k от оптимальной.

Вы можете добавить размер этой IS к общему количеству кликов в вашем решении на данный момент; если это больше, чем текущий UB, вы можете прервать эту подзадачу, поскольку мы знаем, что ее дальнейшее уточнение не может дать лучшего решения, чем то, которое мы уже видели.