Ищем алгоритмы: минимальный разрез для получения двудольного графа

Question

Учитывая неориентированный взвешенный граф (или один связанный компонент большего непересекающегося графа), который обычно будет содержать множество нечетных и четных циклов, я ищу алгоритмы для удаления наименьшего возможного числа ребер, необходимого для получения одного или нескольких двудольных подграфов., Существуют ли в литературе какие-либо стандартные алгоритмы, такие как минимальный разрез и т. Д.?

Проблема, которую я пытаюсь решить, в реальном мире выглядит примерно так: презентации продолжительностью около 1 часа проводятся для студентов по различным предметам в один или два временных блока. Студенты могут подписаться как минимум на одну презентацию по своему выбору, либо на две, либо на три (третий вариант является альтернативой, если одна из других не будет представлена). У них должны быть все разные варианты. Если для данной презентации зарегистрировано менее трех подписчиков, она не будет предоставлена. Если их 18 или более, это будет дано дважды в обоих блоках. Я должен запланировать презентации так, чтобы максимальное количество подписчиков было удовлетворено.

Планирование является тривиальным в следующих случаях:

1. Регистрация только для одной презентации всегда может быть удовлетворена, если презентация дана (т. Е. Регистрация>= 3);

2. Записаться на две презентации всегда можно, если хотя бы одна из них дается дважды.

Во-первых, все регистрации объединяются, чтобы определить, какие из них выдаются один раз, а какие - дважды. Если студент подписался на презентацию с небольшим количеством других подписчиков, будет выбрана альтернативная презентация, если она также будет предоставлена.

В конце дня у меня остался неориентированный взвешенный график, где вершины - это презентации, а ребра - студенты, которые подписались на эту комбинацию презентаций, каждая из которых представлена ​​только один раз. Вес соответствует количеству регистраций для уникальной комбинации презентаций (таким образом избегая параллельных краев).

Если число вершин или представлений составляет около 20 или менее, я придумаю решение для грубой силы, которое заканчивается в приемлемое время. Однако каждая дополнительная вершина удваивает время выполнения этого решения. После 28 или около того, он быстро становится неуправляемым.

В этом году у нас было 37 презентаций, тридцать из которых были даны только один раз и поэтому оказались на графике. То, что я пытаюсь сейчас для больших графиков, следующее:

1. Найти все дискретные компоненты и решить каждый компонент в отдельности;
2. Для каждого компонента рекурсивно удаляйте листовые узлы и ребра моста;
3. Генерация связующего дерева (я использую алгоритм Крускала, который работает очень хорошо), сохраняя удаленные ребра;
4. Создайте фундаментальный набор циклов, добавляя один удаленный край обратно в дерево за раз и удаляя остальную часть дерева;
5. Используя алгоритм Гиббса-Уэлча, я генерирую полный набор всех элементарных циклов, начиная с фундаментального набора, полученного на шаге 4;
6. Подсчитайте количество нечетных и четных циклов, которым принадлежит каждое ребро;
7. Создайте приоритетную очередь ребер (порядок обсуждается ниже) и удаляйте каждое ребро последовательно из его связанного компонента, пока полученный компонент не будет двухсторонним.

Я не могу найти порядок очереди с приоритетами, для которого я могу доказать, что результат был бы таким же приемлемым, как и решение, полученное с использованием метода грубой силы (вероятно, это NP-hard). Тем не менее, я пытаюсь что-то вроде этого:

а. Если ребро принадлежит только нечетным циклам, сначала удалите его;

б. Если ребро принадлежит более четным, чем четным циклам, удалите его перед любыми другими ребрами, которые принадлежат более четным циклам, чем нечетные;

с. Края с наименьшим весом должны быть удалены в первую очередь.

Если ребро принадлежит как нечетному, так и четному циклу, удаление его оставит больший нечетный цикл. Вот почему я их так заказываю. Очевидно, что чем больше число нечетных циклов, к которым принадлежит ребро, тем выше приоритет, но только если затронуты менее четные циклы.

Существуют дополнительные критерии, которые существуют, но их необходимо рассматривать вне проблемы графа; например, удаление ребра эффективно удаляет одну из регистраций для одной из презентаций, поэтому необходимо следить, чтобы количество регистраций не становилось слишком маленьким.

(РЕДАКТИРОВАТЬ: существует также возможность разбить презентации на два блока, у которых почти достаточно регистраций, например, 15-16 вместо 18. Но это означает, что тот, кто дает презентацию, должен будет сделать это дважды, так что это компромисс.)

Спасибо заранее за любые предложения!

Answer 1

Эта задача эквивалентна взвешенной по NP- задаче проблеме максимального разреза, которая требует разбиения вершин на две части так, чтобы максимальное число ребер проходило между частями.

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

maximize (1/2) sum_{ij} w_{ij} (1 - y_i y_j)
subject to
y_i in {±1} for all i

где w_ij вес ненаправленного края ij если присутствует, иначе ноль (поэтому соответствующая переменная и ее ограничение могут быть опущены).