Пересечение матроидов - Matroid intersection

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

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

пример

Позволять г = (U,V,E) быть двудольный граф. Можно определить раздел матроид MU на земле установлен E, в котором набор ребер независим, если никакие два ребра не имеют одинаковых конечных точек в U. Аналогичным образом можно определить матроид MV в котором набор ребер независим, если никакие два ребра не имеют одинаковых конечных точек в V. Любой набор ребер, независимых в обоих MU и MV обладает тем свойством, что никакие два его ребра не имеют общей конечной точки; то есть это соответствие. Таким образом, наибольший общий независимый набор MU и MV это максимальное соответствие в г.

Расширение

Проблема пересечения матроидов становится NP-жесткий когда задействовано три матроида вместо двух.

Одно доказательство этого результата твердости использует сокращение от Гамильтонов путь проблема в ориентированные графы. Учитывая ориентированный граф г с участием п вершины и указанные узлы s и т, проблема гамильтонова пути - это проблема определения того, существует ли простой путь длины п - 1, который начинается в s и заканчивается в т. Без ограничения общности можно предположить, что s не имеет входящих ребер и т не имеет исходящих ребер. Тогда гамильтонов путь существует тогда и только тогда, когда существует набор п - 1 элемент на пересечении трех матроидов на множестве ребер графа: два матроида разбиения, гарантирующих, что внутренняя и исходящая степени выбранного набора ребер равны не более чем одному, и графический матроид из неориентированный граф формируется за счет забвения ориентации краев в г, гарантируя, что выбранный набор кромок не имеет циклов (Валлийский 2010 ).

Еще одна вычислительная проблема на матроидах - проблема четности матроидов, был сформулирован Лоулер (1976) как общее обобщение пересечения матроидов и недвудольного сопоставления графов, однако, хотя это может быть решено за полиномиальное время для линейные матроиды, это NP-сложно для других матроидов и требует экспоненциального времени в матроид оракул модель (Дженсен и Корте 1982 ).

использованная литература

  • Брезовец, Карл; Cornuéjols, Жерар; Гловер, Фред (1986), "Два алгоритма взвешенного пересечения матроидов", Математическое программирование, 36 (1): 39–53, Дои:10.1007 / BF02591988.
  • Айгнер, Мартин; Доулинг, Томас (1971), "Теория согласования для комбинаторных геометрий", Труды Американского математического общества, 158 (1): 231–245, Дои:10.1090 / S0002-9947-1971-0286689-5.
  • Эдмондс, Джек (1970), «Субмодульные функции, матроиды и некоторые многогранники», у Р. Гая; Х. Ханам; Н. Зауэр; J. Schonheim (ред.), Комбинаторные структуры и их приложения (Proc. 1969 Calgary Conference), Гордон и Брич, Нью-Йорк, стр. 69–87.. Перепечатано в M. Jünger et al. (Ред.): Комбинаторная оптимизация (Эдмондс Фестшрифт), LNCS 2570, стр. 1126, Springer-Verlag, 2003.
  • Франк, Андраш (1981), "Взвешенный алгоритм пересечения матроидов", Журнал алгоритмов, 2 (4): 328–336, Дои:10.1016/0196-6774(81)90032-8.
  • Фредериксон, Грег Н .; Шринивас, Мандаям А. (1989), «Алгоритмы и структуры данных для расширенного семейства задач пересечения матроидов», SIAM Журнал по вычислениям, 18 (1): 112–138, Дои:10.1137/0218008.
  • Габоу, Гарольд Н .; Тарджан, Роберт Э. (1984), «Эффективные алгоритмы для семейства задач пересечения матроидов», Журнал алгоритмов, 5 (1): 80–131, Дои:10.1016/0196-6774(84)90042-7.
  • Jensen, Per M .; Корте, Бернхард (1982), "Сложность алгоритмов свойств матроидов", SIAM Журнал по вычислениям, 11 (1): 184–190, Дои:10.1137/0211014, Г-Н  0646772.
  • Лоулер, Юджин Л. (1975), «Алгоритмы пересечения матроидов», Математическое программирование, 9 (1): 31–56, Дои:10.1007 / BF01681329.
  • Лоулер, Юджин Л. (1976), «Глава 9: Проблема четности Matroid», Комбинаторная оптимизация: сети и матроиды, Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 356–367, Г-Н  0439106.
  • Валлийский, Д. Дж. А. (2010) [1976], Матроид Теория, Courier Dover Publications, стр. 131, ISBN  9780486474397.