Направленное максимальное взвешенное двухпартийное соответствие, позволяющее разделять начальные/конечные вершины

Пусть G (U u V, E) - взвешенный ориентированный двудольный граф (т.е. U и V - два набора узлов двудольного графа, а E содержит направленные взвешенные ребра из U в V или из V в U). Вот пример:

bipartite directed and weighted graph

В этом случае:

U = {A,B,C} 
V = {D,E,F} 
E = {(A->E,7), (B->D,1), (C->E,3), (F->A,9)}

Определение: DirectionalMatching (я сформулировал этот термин только для того, чтобы сделать все более ясным): набор направленных ребер, которые могут делиться начальными или конечными вершинами. То есть, если U- > V и U '- > V' оба относятся к DirectionalMatching, то V/= U 'и V'/= U, но может быть, что U = U 'или V = V'.

Мой вопрос: Как эффективно найти DirectionalMatching, как определено выше, для двудольного ориентированного взвешенного графика, который максимизирует сумму весов его ребер?

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

В приведенном выше примере максимальное взвешенное управление направлением: {F- > A, C- > E, B- > D} со значением 13.

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

Спасибо!

Примечание 1: Этот вопрос основан на Максимально взвешенном двудольном сопоставлении _with_ направленных ребер, но с дополнительной релаксацией, которая разрешена для ребер в сопоставлении для совместного использования источника или адресата. Поскольку эта релаксация имеет большое значение, я создал независимый вопрос.

Примечание 2: Это максимальный вес. Мощность (количество ребер присутствует), а количество вершин, покрываемых совпадением, не имеет значения для правильного результата. Учитывается только максимальный вес.

Примечание 2: Во время моего исследования, чтобы решить проблему, я нашел эту статью, я думаю, что было бы полезно, если другие попытаются найти решение: Чередование циклов и путей в красном цвете мультиграфы: обзор

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

Примечание 4: Я подозреваю, что проблема может быть NP-жесткой, но я не так разбираюсь в сокращениях, поэтому мне еще не удалось это доказать.

Еще один пример:

Представьте, что вы имели

4 вершины: {u1, u2} {v1, v2}

4 ребра: {u1->v1, u1->v2, u2->v1, v2->u2}

Тогда, независимо от их веса, u1->v2 и v2->u2 не могут находиться в одном и том же методе DirectionalMatching, не могут v2->u2 и u2->v1. Однако u1->v1 и u1->v2 могут, и поэтому могут u1->v1 и u2->v1.

Ответы

Ответ 1

Определите новый неориентированный граф G' из G следующим образом.

  • G' имеет node (A, B) с весом w для каждого направленного ребра (A, B) с весом w в G
  • G' имеет неориентированный ребро ((A, B),(B, C)), если (A, B) и (B, C) оба являются направленными ребрами в G

http://en.wikipedia.org/wiki/Line_graph#Line_digraphs

Теперь найдите максимальное (взвешенное) независимое множество вершин в G'.

http://en.wikipedia.org/wiki/Vertex_independent_set

Изменить: материал после этой точки работает только в том случае, если все весы ребер одинаковы - когда весы ребер имеют разные значения, это более сложная проблема ( "максимальный весовой набор вершин" для Google для возможных алгоритмов)

Обычно это будет NP-трудная проблема. Однако G' - двудольный граф - он содержит только четные циклы. Поиск максимального (взвешенного) независимого набора вершин в двудольном графе не является NP-трудным.

Алгоритм, который вы будете запускать на G', выглядит следующим образом.

  • Найдите связанные компоненты G', скажем H_1, H_2, ..., H_k
  • Для каждого H_i выполните 2-цветные (например, красные и синие) узлы. Подход поваренной книги здесь заключается в том, чтобы выполнить поиск по глубине в H_i чередующихся цветах. Простым подходом было бы цвет каждой вершины в H_i на основе того, соответствует ли соответствующее ребро в G от U до V (красное) или от V до U (синее).
  • Два варианта выбора узлов из H_i - это либо все красные узлы, либо все синие узлы. Выберите цветной node с более высоким весом. Например, красный набор node имеет вес, равный H_i.nodes.where(node => node.color == red).sum(node => node.w). Вызовите более высокий вес node set N_i.
  • Ваше максимальное взвешенное независимое множество вершин теперь union(N_1, N_2, ..., N_k).

Так как каждая вершина в G' соответствует одному из направленных ребер в G, у вас есть максимальный DirectionalMatching.

Ответ 2

Эта проблема может быть решена в полиномиальное время, используя Венгерский алгоритм. "Доказательство" Vor выше неверно.

Метод структурирования проблемы для приведенного выше примера выглядит следующим образом:

   D E F
A  # 7 9  
B  1 # #
C  # 3 #

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