Максимально независимый набор двудольного графа

19

Я пытаюсь найти максимальный независимый набор бипаритового графа.

В некоторых заметках я обнаружил следующее: «13 мая 1998 г. - Вашингтонский университет - CSE 521 - Приложения сетевого потока» :

Проблема:

Для двудольного графа G=(U,V,E) найдите как можно большее независимое множество UV , где UU и VV . Множество является независимым, если между элементами множества нет ребер E

Решение:

Построить потоковый граф на вершинах UV{s,t} . Для каждого ребра (u,v)E существует бесконечное ребро емкости от u до v . Для каждого uU существует ребро единичной емкости от s до u , а для каждого vV существует ребро единичной емкости от v до t .

Найти конечный разрез емкости (S,T) , с sS и tT . Пусть U=US и V=VT . Множество UV является независимым, поскольку не существует бесконечных ребер емкости, пересекающих разрез. Размер разреза составляет |UU|+|VV|=|U|+|V||UV|, Это делается для того, чтобы сделать независимый набор как можно большим, мы делаем разрез как можно меньшим.

Итак, давайте возьмем это как график:

A - B - C
    |
D - E - F

Мы можем разбить это на двудольный граф следующим образом (U,V)=({A,C,E},{B,D,F})

По поиску методом грубой силы мы можем видеть, что единственный Максимальный Независимый Набор - это A,C,D,F . Давайте попробуем разобраться с решением выше:

Таким образом, построенная матрица смежности потоковой сети будет:

stABCDEFs00101010t00010101A1000000B01000C1000000D0100000E10000F0100000

Вот где я застрял, наименьшее конечное снижение производительности, которое я вижу, является тривиальным: (S,T)=({s},{t,A,B,C,D,E,F}) с мощностью 3.

Использование этого разреза приводит к неверному решению:

U=US={}
V=VT={B,D,F}
UV={B,D,F}

В то время как мы ожидали UV={A,C,D,F} ? Может кто-нибудь определить, где я ошибся в своих рассуждениях / работе?

Андрей Томазос
источник
(S, T) = ({s, A, B, C}, {t, D, E, F}) имеет емкость 2
1
@ Брайан, существует бесконечное ребро емкости от B до E по вашему разрезу, так что это бесконечное пространство.
Эндрю Томазос
если я правильно понимаю, исходя из решения грубой силы, вам нужен разрез, где S содержит A и C, а T содержит D и F, что делает ваш разрез {s, A, C}, {t, D, F} , Теперь, как вы строите разрез?
njzk2
Кроме того, это похоже на Ford-Fulkerson, у которого края имеют емкость один.
njzk2
Посмотрите на венгерский алгоритм.
Патрик Vörös

Ответы:

14

Дополнением максимального независимого множества является минимальное покрытие вершин.

Чтобы найти минимальное покрытие вершин в двудольном графе, см . Теорему Кенига .

Юкка Суомела
источник
2
Это (возможно) решает проблему, но не отвечает на вопрос.
Рафаэль
2
@ Рафаэль: Я согласен, если вы удалите слово «возможно». :)
Юкка Суомела
1
О, я уверен , что он решает на проблему, но я не уверен , помогает ли Эндрю решить его проблему.
Рафаэль
3
Я решил это так, как вы предлагаете: HopcroftKarp -> максимальное соответствие -> Konigs Thereom -> Минимальное покрытие вершин -> Дополнение -> Максимальный независимый набор. Я все еще хотел бы знать, почему метод потока, описанный в моем вопросе, кажется, не работает.
Эндрю Томазос
5

Данное решение явно неверно, как вы продемонстрировали на контрпримере. Отметим, что граф U + V является связным компонентом ребрами бесконечной емкости. Поэтому каждый действительный разрез должен содержать все буквы A, B, C, D, E, F на одной стороне.

Попытка отследить, откуда пришло решение: http://www.cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf цитирует сетевые потоки Ахуджи, Магнанти и Орлина для решения некоторых проблем. На эту книгу не распространяются авторские права и ее можно загрузить с http://archive.org/details/networkflows00ahuj, но в ней, похоже, нет этой проблемы и ее решения (поиск для каждого случая "двудольного").

Обратите внимание, что пояснительный параграф решения не показывает, что наименьший разрез построенного им графика соответствует максимальному независимому набору. Это только показывает способ получить в самостоятельный набор.

И все же, вы можете увидеть, что пытается сделать алгоритм. Вот что соответствует фактическому максимальному независимому набору с точки зрения его s, t cut:

график

Подчеркнуто ребро с бесконечной емкостью, нарушающее алгоритм.

Я не уверен, как исправить алгоритм в соответствии с тем, что было задумано. Может быть, стоимость бесконечного ребра должна быть равна нулю, если он идет в обратном направлении (т. Е. Куда он идет от S к T, но пересекает от t-стороны к s-стороне)? Но все же легко найти минимальный срез / максимальный поток с этой нелинейностью? Кроме того, если подумать о том, как соединить решение @Jukka Suomela с алгоритмом из этого вопроса, возникает трудность, когда мы переходим от максимального соответствия к минимальному покрытию вершин: в то время как нахождение максимального соответствия можно сделать с помощью максимального потока -подобный алгоритм, как вы восстанавливаете минимальное покрытие вершин из него, используя подобный потоку алгоритм? Как описано здесьпосле того, как максимальное совпадение найдено, ребра между U и V становятся направленными, чтобы найти минимальное покрытие вершин. Итак, опять же, это не показывает, что для решения этой проблемы достаточно простого применения min-cut / max-flow.

Евгений Сергеев
источник
2

Данный алгоритм корректен. Построенная сеть потока должна быть направлена, и значениеS-T вырезать учитывает только ребра, выходящие из множества вершин S,

yu25x
источник
1
Я согласен с вами, но не могли бы вы добавить более подробную информацию, например, полное доказательство правильности алгоритма потока и то, как алгоритм применяется на примере ОП?
xskxzr
Примечание в этом есть краткое доказательство правильности. cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf Например, если вы посмотрите на рисунок Евгения Сергеева выше, все края должны быть направлены вниз. Тогда только два ребра из S - это (s, e) и (b, t), жирный красный край входит в S и не должен учитываться в значении среза.
yu25x
0

Срез должен быть на фактическом потоке, а не на производительности. Поскольку поток из s конечен, любой {S, T} разрез будет конечным. Остальное объяснено выше.

Talmon
источник
1
Вы уверены? Сокращения, как правило, производятся по мощностям, и, в любом случае, мы уже знаем, что минимальный разрез является конечным, так что сокращение порезов, похоже, не является проблемой.
Дэвид Ричерби
0

Я думаю, что вам не нужно соединять ребра в обоих направлениях, даже если исходный график был ненаправленным. Поскольку для сети потоков вам нужен ориентированный граф, вы можете рассмотреть только ребра изU в В,

Тогда в этом новом графике грамм', у вас будет мин-2, что дает вам ответ {A,С,D,F},

Аджит Кумар
источник