Алгоритм разделить двусторонний граф в подграфы

Question

Я ищу алгоритм, чтобы разделить двусторонний граф в подграфы с определенным ограничением. Я не уверен, что какие-либо существующие алгоритмы решают мою проблему или нет.

У меня есть неопроверенный двусторонний график, где узлы являются клиентами ( $ C $ ) и услуги ( $ S $ < / span>). Я хочу разделить это на несколько небольших подграфов, ограничивая количество услуг в каждом подгребе до некоторого максимального количества $ n $ . К сожалению, в поисках отключенных подграфов недостаточно, потому что график подключения слишком высока, поэтому мне понадобится дублировать услуги.

формально, я хочу набор подграфов таких, что:

.
• каждый клиент $ c \ in c $ появляется в ровно в одном подграфе
• все края появляются в ровно в одном подграфе (тот, в котором появляется их клиент)
• Каждый сервис $ s \ in s $ может появиться в любом количестве подграфов (в порядке дублирующих служб, чтобы помочь разделению)
• Каждый подграф должен иметь максимально возможное $ n $ Услуги (где $ n $ - данная постоянная Это гарантированно будет больше, чем наибольшее количество услуг, подключенных к любому одному клиенту)
• Подграфы должны иметь как можно больше клиентов (без этого ограничения, это тривиально разрешимо, помещая каждого клиента в собственный подграф с копией их услуг). Это может быть эвристическим, а не формально доказанным.

Может кто-нибудь предложить алгоритму для этого? Количество узлов не является огромным (примерно 1000 клиентов, 100 услуг, с каждым клиентом, подключенным к 5 или меньшим количеством услуг), поэтому приближается к грубой силе или те, что с плохим масштабированием Big-O может подходить.

Answer 1

Пахнет так, как будто это может быть NP-Hard.

Один правдоподобный подход - использовать SAT Solver или Rolver ILP.Предположим, вы решаете, что вы хотите иметь максимально возможное значение $ m $ .Тогда у вас могут быть логические переменные $ x_ {i, k}, y_ {j, k} $ Указание того, что клиент $ I$ переходит в подграф $ K $ and Service $ j $ переходит в подграф $ k $ .Вы можете получить кучу ограничений (пунктов) на основе ваших требований, а затем спросить SAT Solver или Rolver ILP, чтобы найти возможное решение.Время работы в худшем случае экспоненциально.Это может или не может работать достаточно хорошо в вашей ситуации.