Существует известное и элегантное сокращение от проблемы максимального согласования по двум частям до проблемы максимального потока: мы создаем сеть с исходным узлом , терминальным узлом и одним узлом для каждого сопоставляемого элемента, затем добавляем соответствующие ребра.
Конечно, есть способ уменьшить максимальный поток до максимального соответствия двудольных за полиномиальное время, поскольку каждый из них может быть решен по отдельности за полиномиальное время. Тем не менее, есть ли "хорошее" сокращение за полиномиальное время от максимального потока (в общих графах) до максимального двудольного соответствия?
reductions
network-flow
bipartite-matching
templatetypedef
источник
источник
Ответы:
Как ни странно, такое сокращение не известно. Однако в недавней работе Madry (FOCS 2013) было показано, как уменьшить максимальный поток в графах с единичной емкостью до (логарифмически многих случаев) максимального в двудольных графах.b
В случае, если вы не знакомы с проблемой максимального , это обобщение сопоставления, определяемое следующим образом: входными данными является граф (в нашем случае двудольный граф), G = ( V , E ) и множество интегральных требований для каждой вершины, причем требование вершины v обозначается через b v . Цель состоит в том, чтобы найти максимально возможное множество ребер S , чтобы ни у одной вершины v не было больше, чем b v ребер в S, падающих на vb G=(V,E) v bv S v bv S v , Это простое упражнение обобщить сокращение от двудольного согласования до максимума потоков и показать аналогичное сокращение от двудольного Сопоставления до максимума потоков. (Один из) удивительных результатов (результатов) статьи Мадри состоит в том, что в некотором смысле эти проблемы эквивалентны, давая простое сокращение, которое уменьшает максимальный поток в графах единичных мощностей (обычно графах, где сумма мощностей, | u | 1 является линейным по числу ребер, m ) задаче b-соответствия в графе с O ( m ) узлами, вершинами и суммой требований.б | ты |1 м б O ( м )
Если вас интересуют подробности, см. Раздел 3, вплоть до теоремы 3.1 и раздела 4 (и подтверждение правильности в Приложении C) версии статьи Мадри на ArXiv, здесь . Если терминология не является самоочевидной, см. Раздел 2.5 для краткого обзора проблемы и имейте в виду, что u e - это емкость ребра e в исходном экземпляре максимального потока.б Uе е
источник
Вот попытка ответить на ваш вопрос:
Я имею в виду, что это все, на мой взгляд, что вы задали в вопросе, и это мой потенциальный ответ :).
источник