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

Общий независимый набор из двух матроидов

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

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

Примеры

Пусть G  = ( U , V , E ) — двудольный граф . Можно определить матроид разбиения M _U на базовом множестве E , в котором набор ребер независим, если никакие два ребра не имеют одинаковой конечной точки в U . Аналогично можно определить матроид M _{V ,} в котором набор ребер независим, если никакие два ребра не имеют одинаковой конечной точки в V . Любой набор ребер, который независим как в M _U , так и в M _{V ,} обладает тем свойством, что никакие два его ребра не имеют общей конечной точки; то есть он является паросочетанием . Таким образом, наибольшее общее независимое множество M _U и M _V является максимальным паросочетанием в G .

Аналогично, если каждое ребро имеет вес, то независимый набор максимального веса M _U и M _V является паросочетанием максимального веса в G .

Алгоритмы

Существует несколько алгоритмов полиномиального времени для взвешенного пересечения матроидов с различным временем выполнения. Время выполнения указывается в терминах - количества элементов в общем базовом наборе, - максимального между рангами двух матроидов, - количества операций, необходимых для оракула поиска контуров , и - количества элементов в пересечении (в случае, если мы хотим найти пересечение определенного размера ). ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle T}$ ${\displaystyle k}$ ${\displaystyle k}$

• Алгоритм Эдмондса использует линейное программирование и многогранники. ^[1]
• Алгоритм Лоулера . ^[2]
• Алгоритм Ири и Томизавы ^[3]
• Алгоритм Андраша Франка ^[4] использует арифметические операции. ${\displaystyle O(n^{3}T)}$
• Алгоритм Орлина и Ванде-Вейта. ^[5]
• Алгоритм Каннингема ^[6] требует операций над общими матроидами и операций над линейными матроидами для двух матриц размером r на n . ${\displaystyle O(r^{1.5}nT)}$ ${\displaystyle O(nr^{2}\log {r})}$
• Брезовец, Корнуэхос и Гловер ^[7] представляют два алгоритма для взвешенного пересечения матроидов.
  • Первый алгоритм требует, чтобы все веса были целыми числами, и находит пересечение мощности за время . ${\displaystyle k}$ ${\displaystyle O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))}$
  • Второй алгоритм работает во времени . ${\displaystyle O(nr\cdot (\log {n}+r+T))}$
• Хуанг, Какимура и Камияма ^[8] показывают, что задача взвешенного пересечения матроидов может быть решена путем решения W экземпляров задачи невзвешенного пересечения матроидов, где W — наибольший заданный вес, предполагая, что все заданные веса являются целыми. Этот алгоритм быстрее предыдущих алгоритмов, когда W мало. Они также представляют алгоритм приближения, который находит e -приближенное решение путем решения экземпляров задачи невзвешенного пересечения матроидов, где r — меньший ранг двух входных матроидов. ${\displaystyle O(\epsilon ^{-1}\log {r})}$
• Гош, Гурджар и Радж ^[9] изучают сложность выполнения пересечения матроидов в модели параллельных вычислений .
• Берци, Кирай, Ямагучи и Ёкои ^[10] представляют сильно полиномиальные алгоритмы для взвешенного пересечения матроидов с использованием более ограниченных оракулов.

Расширения

Максимизация веса в зависимости от мощности

В варианте взвешенного пересечения матроидов, называемом "(P _k )", цель состоит в том, чтобы найти общее независимое множество с максимально возможным весом среди всех таких множеств с мощностью k , если такое множество существует. Этот вариант также может быть решен за полиномиальное время. ^[7]

Три матроида

Задача пересечения матроидов становится NP-трудной , когда задействованы три матроида, а не только два.

Одно доказательство этого результата о сложности использует редукцию из задачи о гамильтоновом пути в ориентированных графах . При заданном ориентированном графе G с n вершинами и указанными узлами s и t задача о гамильтоновом пути — это задача определения, существует ли простой путь длины n  − 1, который начинается в s и заканчивается в t . Можно предположить без потери общности, что s не имеет входящих ребер, а t не имеет исходящих ребер. Тогда гамильтонов путь существует тогда и только тогда, когда существует набор из n  − 1 элементов в пересечении трех матроидов на множестве ребер графа: два матроида разбиения, гарантирующие, что входящая и исходящая степени выбранного множества ребер не превышают единицу, и графический матроид неориентированного графа, образованный путем забывания ориентаций ребер в G , гарантирующий, что выбранное множество ребер не имеет циклов. ^[11]

Матроидная четность

Другая вычислительная проблема на матроидах, проблема четности матроидов , была сформулирована Лоулером ^[12] как общее обобщение пересечения матроидов и сопоставления недвудольных графов. Однако, хотя она может быть решена за полиномиальное время для линейных матроидов , она является NP-трудной для других матроидов и требует экспоненциального времени в модели оракула матроидов . ^[13]

Оцененные матроиды

Оцененный матроид — это матроид, снабженный функцией значения v на множестве своих баз, со следующим свойством обмена : для любых двух различных баз и , если , то существует элемент, такой что и являются базами, и : . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle a\in A\setminus B}$ ${\displaystyle b\in B\setminus A}$ ${\displaystyle (A\setminus \{a\})\cup \{b\}}$ ${\displaystyle (B\setminus \{b\})\cup \{a\}}$ ${\displaystyle v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})}$

При наличии взвешенного двудольного графа G = ( X + Y , E ) и двух оцененных матроидов, одного на X с базами B _X и оценкой v _X , и одного на Y с базами B _Y и оценкой v _Y , оцененная независимая задача присваивания — это задача нахождения соответствия M в G , такого, что M _X (подмножество X, сопоставленное с M ) является базой в B _X , M _Y является базой в B _Y , и при условии этого сумма максимизируется. Взвешенная задача пересечения матроидов — это особый случай, в котором оценки матроидов постоянны, поэтому мы стремимся максимизировать только при условии, что M _X является базой в B _X и M _Y является базой в B _Y . ^[14] Мурота представляет полиномиальный алгоритм для этой задачи. ^[15] ${\displaystyle w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})}$ ${\displaystyle w(M)}$

Смотрите также

• Разбиение матроида — родственная проблема.

Ссылки

1. Edmonds, Jack (1970), «Субмодулярные функции, матроиды и некоторые многогранники», в R. Guy; H. Hanam; N. Sauer; J. Schonheim (ред.), Комбинаторные структуры и их приложения (Proc. 1969 Calgary Conference) , Gordon and Breach, Нью-Йорк, стр. 69–87. Перепечатано в M. Junger et al. (Ред.): Комбинаторная оптимизация (Edmonds Festschrift), LNCS 2570, стр. 1126, Springer-Verlag, 2003.
2. Лоулер, Юджин Л. (1975), «Алгоритмы пересечения матроидов», Математическое программирование , 9 (1): 31–56, doi :10.1007/BF01681329, S2CID  206801650
3. Ири, Масао; Томизава, Нобуаки (1976). «Алгоритм поиска оптимального «независимого задания» » . 19 (1): 32–57. дои : 10.15807/jorsj.19.32 .
4. Франк, Андраш (1981), «Взвешенный алгоритм пересечения матроидов», Журнал алгоритмов , 2 (4): 328–336, doi :10.1016/0196-6774(81)90032-8
5. Орлин, Джеймс Б.; Вандевейт, Джон (1983). Об алгоритме пересечения «первичных» матроидов (рабочий документ Школы менеджмента Слоуна № 1446-83). hdl :1721.1/2050.
6. Каннингем, Уильям Х. (1 ноября 1986 г.). «Улучшенные границы для алгоритмов разбиения и пересечения матроидов». Журнал SIAM по вычислениям . 15 (4): 948–957. doi :10.1137/0215066. ISSN  0097-5397.
7. Brezovec, Carl; Cornuéjols, Gérard ; Glover, Fred (1986), "Два алгоритма для взвешенного пересечения матроидов", Mathematical Programming , 36 (1): 39–53, doi :10.1007/BF02591988, S2CID  34567631
8. Хуан, Цзянь-Чунг; Какимура, Наонори; Камияма, Наоюки (2019-09-01). «Точные и приближенные алгоритмы для взвешенного пересечения матроидов». Математическое программирование . 177 (1): 85–112. doi :10.1007/s10107-018-1260-x. hdl : 2324/1474903 . ISSN  1436-4646. S2CID  254138118.
9. Гош, Суманта; Гурджар, Рохит; Радж, Рошан (2022-01-01), «Детерминированное параллельное сокращение от поиска пересечения взвешенных матроидов к решению», Труды ежегодного симпозиума ACM-SIAM 2022 года по дискретным алгоритмам (SODA) , Труды, Общество промышленной и прикладной математики, стр. 1013–1035, doi : 10.1137/1.9781611977073.44, ISBN 978-1-61197-707-3, S2CID  245799113 , получено 2022-11-28
10. Берчи, Кристоф; Кирай, Тамаш; Ямагучи, Ютаро; Ёкои, Ю (28 сентября 2022 г.). «Пересечение матроидов под ограниченными оракулами». arXiv : 2209.14516 [cs.DS].
11. Валлийский, DJA (2010) [1976], Теория Матроидов , Courier Dover Publications, стр. 131, ISBN 9780486474397.
12. Лоулер, Юджин Л. (1976), «Глава 9: Проблема четности матроидов», Комбинаторная оптимизация: сети и матроиды , Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 356–367, MR  0439106.
13. Йенсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi :10.1137/0211014, MR  0646772.
14. Мурота, Казуо (1996-11-01). «Оцененное пересечение матроидов I: критерии оптимальности». Журнал SIAM по дискретной математике . 9 (4): 545–561. doi :10.1137/S0895480195279994. ISSN  0895-4801.
15. Мурота, Кадзуо (ноябрь 1996 г.). «Пересечение оцененного матроида II: Алгоритмы». SIAM Journal по дискретной математике . 9 (4): 562–576. дои : 10.1137/S0895480195280009. ISSN  0895-4801.

Дальнейшее чтение

• Айгнер, Мартин; Доулинг, Томас (1971), «Теория соответствия для комбинаторных геометрий», Труды Американского математического общества , 158 (1): 231–245, doi : 10.1090/S0002-9947-1971-0286689-5.
• Фредериксон, Грег Н.; Шринивас, Мандаям А. (1989), «Алгоритмы и структуры данных для расширенного семейства задач пересечения матроидов» (PDF) , SIAM Journal on Computing , 18 (1): 112–138, doi :10.1137/0218008, hdl :1802/6137, архивировано из оригинала 22 сентября 2017 г..
• Габов, Гарольд Н.; Тарьян , Роберт Э. (1984), «Эффективные алгоритмы для семейства задач пересечения матроидов», Журнал алгоритмов , 5 (1): 80–131, doi :10.1016/0196-6774(84)90042-7..