Проблема с четностью Матроида

В комбинаторной оптимизации проблема четности матроида — это проблема поиска наибольшего независимого набора парных элементов в матроиде . ^{[ 1 ]} Проблема была сформулирована Лоулером (1976) как общее обобщение сопоставления графов и пересечения матроидов . ^{[ 1 ]}^{[ 2 ]} Это также известно как сопоставление полиматроидов или проблема сопоставления . ^{[ 3 ]}

четность матроидов может быть решена за полиномиальное время Для линейных матроидов . Однако для некоторых компактно представленных матроидов это NP-трудно и требует более чем полиномиального числа шагов в модели матроида-оракула . ^{[ 1 ]}^{[ 4 ]}

Приложения алгоритмов четности матроидов включают поиск больших плоских подграфов. ^{[ 5 ]} и нахождение графовых вложений максимального рода . ^{[ 6 ]} Эти алгоритмы также можно использовать для поиска связных доминирующих множеств и множеств вершин обратной связи в графах максимальной степени три. ^{[ 7 ]}

Формулировка

Матроид : может быть определен из конечного набора элементов и исходя из понятия того, что означает независимость подмножеств элементов, с учетом следующих ограничений

Каждое подмножество независимого множества должно быть независимым.
Если $S$ и $T$ являются независимыми множествами, причем $|T|>|S|$ , то существует элемент $t\in T$ такой, что $S\cup \{t\}$ является независимым. ^{[ 1 ]}

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

В задаче о четности матроидов входные данные состоят из матроида вместе с парой его элементов, так что каждый элемент принадлежит одной паре. Цель состоит в том, чтобы найти как можно большее подмножество пар, чтобы объединение пар в выбранном подмножестве было независимым. ^{[ 1 ]}^{[ 2 ]} Другой, казалось бы, более общий вариант, в котором допустимые пары образуют граф, а не только одна пара на элемент, эквивалентен: элемент, появляющийся более чем в одной паре, может быть заменен несколькими копиями элемента, по одной на пару. ^{[ 8 ]}

Алгоритмы

Проблема матроидной четности для линейных матроидов может быть решена с помощью рандомизированного алгоритма по времени. $O(nr^{\omega -1})$ , где $n$ — количество элементов матроида, $r$ - его ранг (размер наибольшего независимого множества), а $\omega$ — показатель степени в пределах времени для быстрого умножения матриц . ^{[ 1 ]} В частности, используя алгоритм умножения матриц Ле Галля, ^{[ 9 ]} это можно решить со временем $O(nr^{1.3729})$ . Без использования быстрого умножения матриц задача четности линейного матроида может быть решена за время $O(nr^{2})$ . ^{[ 1 ]}

Эти алгоритмы основаны на в линейной алгебре формулировке проблемы, сформулированной Гиленом и Иватой (2005) . Предположим, что входные данные задачи состоят из $m$ пары $r$ -мерные векторы (упорядоченные как векторы-столбцы в матрице $M$ размера $r\times 2m$ ). Тогда число пар в оптимальном решении равно

{\frac {1}{2}}\operatorname {rank} {\begin{pmatrix}0&M\\M^{T}&T\end{pmatrix}}-m,

где $T$ представляет собой блочную диагональную матрицу , блоки которой $2\times 2$ подматрицы формы

{\begin{pmatrix}0&t_{i}\\-t_{i}&0\end{pmatrix}}

для последовательности переменных $t_{1},\dots t_{m}$ . ^{[ 10 ]} Лемму Шварца – Циппеля можно использовать для проверки того, имеет ли эта матрица полный ранг или нет (т. е. имеет ли решение размер $r/2$ или нет), присваивая переменным случайные значения $t_{i}$ и проверка того, имеет ли результирующая матрица нулевой определитель . Применяя жадный алгоритм , который удаляет пары по одной, устанавливая их неопределенные значения равными нулю, пока матрица остается полного ранга (сохраняя обратную матрицу с использованием формулы Шермана-Моррисона для проверки ранга после каждого удаления), можно найти решение всякий раз, когда этот тест показывает, что оно существует. Дополнительные методы расширяют этот алгоритм на случай, когда оптимальное решение проблемы четности матроидов имеет менее $r/2$ пары. ^{[ 1 ]}

Для графических матроидов известны более эффективные алгоритмы, с временем работы $O(mn\log ^{6}n)$ на графиках с $m$ вершины и $n$ края. ^{[ 11 ]} Для простых графиков $m$ является $O(n^{2})$ , но для мультиграфов оно может быть больше, поэтому также интересно иметь алгоритмы с меньшей зависимостью или вообще без зависимости от $m$ и худшая зависимость от $n$ . В этих случаях также возможно решить проблему четности графического матроида за рандомизированное ожидаемое время. $O(n^{4})$ , или во времени $O(n^{3})$ когда каждая пара ребер образует путь. ^{[ 1 ]}

Хотя проблема четности матроидов является NP-трудной для произвольных матроидов, ее все же можно эффективно аппроксимировать. Простые алгоритмы локального поиска обеспечивают схему аппроксимации этой задачи за полиномиальное время и находят решения, размер которых как доля оптимального размера решения сколь угодно близок к единице. Алгоритм начинается с пустого набора в качестве решения и неоднократно пытается увеличить размер решения на единицу, удаляя не более чем постоянное число. $C$ пар из решения и заменяя их другим набором еще одной парой. Когда такие ходы больше невозможны, полученное решение возвращается как приближение к оптимальному решению. Для достижения коэффициента аппроксимации $1-\epsilon$ , достаточно выбрать $C$ быть примерно $5^{\lceil 1/2\epsilon \rceil }$ . ^{[ 8 ]}

Приложения

Многие другие задачи оптимизации могут быть сформулированы как линейные задачи на четность матроида и решены за полиномиальное время с использованием этой формулировки.

Сопоставление графиков

Максимальное совпадение в графе — это как можно большее подмножество ребер, среди которых нет двух, имеющих общую конечную точку. Ее можно сформулировать как задачу о четности матроида в матроиде разбиения, который имеет элемент для каждой инцидентности вершины и ребра в графе. В этом матроиде два элемента считаются парными, если они являются двумя инцидентностями одного и того же ребра друг друга. Подмножество элементов является независимым, если оно имеет не более одного инцидентности для каждой вершины графа. Парами элементов в решении проблемы четности матроида для этого матроида являются инцидентности между ребрами в максимальном паросочетании и их конечными точками. ^{[ 2 ]}

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

Экземпляр задачи пересечения матроидов состоит из двух матроидов из одного и того же набора элементов; цель состоит в том, чтобы найти как можно большее подмножество элементов, независимое в обоих матроидах. Чтобы сформулировать пересечение матроидов как проблему четности матроидов, постройте новый матроид, элементы которого представляют собой непересекающееся объединение двух копий данных элементов, по одной для каждого входного матроида. В новом матроиде подмножество является независимым, если его ограничение на каждую из двух копий независимо в каждом из двух матроидов соответственно. Соедините элементы нового матроида так, чтобы каждый элемент был связан со своей копией. Пары элементов в решении проблемы четности матроида для этого матроида представляют собой две копии каждого элемента в решении проблемы пересечения матроида. ^{[ 2 ]}

Большие плоские подграфы

В произвольном графе задачу поиска наибольшего набора треугольников в данном графе без циклов, отличных от выбранных треугольников, можно сформулировать как задачу о четности матроида на графическом матроиде, элементами которого являются ребра графа с одним пара ребер на треугольник (дублирование ребер при необходимости, если они принадлежат более чем одному треугольнику). Парами элементов решения проблемы четности матроида для этого матроида являются два ребра в каждом треугольнике оптимального набора треугольников. Ту же проблему можно также описать как задачу поиска наибольшего ациклического по Бержу подгиперграфа 3-равномерного гиперграфа . В версии задачи с гиперграфом гиперребра представляют собой треугольники данного графа. ^{[ 3 ]}

Граф кактуса — это граф, в котором каждые два цикла имеют не более одной общей вершины. В частном случае графы, в которых каждый цикл является треугольником, обязательно являются графами-кактусами. Самый большой треугольный кактус на данном графике затем может быть найден путем добавления дополнительных ребер из остовного дерева без создания новых циклов, так что результирующий подграф будет иметь те же компоненты связности , что и исходный граф. Графы кактусов автоматически являются плоскими графами , и проблема поиска треугольных графов кактусов формирует основу для лучшего известного алгоритма аппроксимации проблемы поиска наибольшего плоского подграфа данного графа, что является важным шагом в планаризации . Самый большой треугольный кактус всегда имеет как минимум 4/9 количества ребер самого большого плоского подграфа, что улучшает коэффициент аппроксимации 1/3, полученный при использовании произвольного остовного дерева. ^{[ 5 ]}

Комбинаторная жесткость

Каркас из жестких стержней в евклидовой плоскости , соединенных в своих концах гибкими шарнирами, можно зафиксировать в одном положении на плоскости, прикрепив некоторые из его шарниров к точкам плоскости. Минимальное количество соединений, которое необходимо закрепить для фиксации каркаса, называется числом закрепки. Его можно вычислить на основе решения связанной проблемы четности матроидов. ^{[ 3 ]}

Вложения максимального рода

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

Чтобы сформулировать задачу поиска дерева Сюонга как задачу матроида на четность, сначала разделите каждое ребро $e$ данного графа в путь, длина которого равна числу других ребер, инцидентных этому графу. $e$ . Затем соедините ребра подразделенного графа в пары так, чтобы каждая пара ребер исходного графа была представлена одной парой ребер в подразделенном графе, и каждое ребро в подразделенном графе было спарено ровно один раз. Решите проблему четности матроида с парными ребрами подразделенного графа, используя его кографический матроид (линейный матроид, в котором подмножество ребер является независимым, если его удаление не разделяет граф). Любое остовное дерево исходного графа, не имеющее ребер, используемых в решении по четности матроида, обязательно является деревом Сюонга. ^{[ 6 ]}

Связанное доминирование

Связное доминирующее множество в графе — это подмножество вершин, индуцированный подграф которого связен, смежный со всеми остальными вершинами. В произвольных графах NP-трудно найти наименьшее связное доминирующее множество, но его можно найти за полиномиальное время для графов максимальной степени три. В кубическом графе можно заменить каждую вершину путем с двумя ребрами, соединенным с концами трех его конечных точек, и сформулировать задачу матроидной четности для пар ребер, сгенерированных таким образом, используя кографический матроид расширенного графа. Вершины, пути которых не используются в решении, образуют минимальное связное доминирующее множество. В графе максимальной степени три некоторые простые дополнительные преобразования сводят задачу к задаче на кубическом графе. ^{[ 7 ]}

Набор вершин обратной связи

в Набор вершин обратной связи графе — это подмножество вершин, которое касается всех циклов. В кубических графах существует линейное уравнение, связывающее количество вершин, цикломатическое число , количество компонентов связности, размер минимального доминирующего набора связностей и размер минимального набора вершин обратной связи. ^{[ 12 ]} Отсюда следует, что та же проблема матроидной четности, которая используется для поиска связных доминирующих множеств, также может быть использована для поиска множеств вершин обратной связи в графах максимальной степени три. ^{[ 7 ]}

Твердость

Задача клики : найти $k$ -вершинный полный подграф в заданном $n$ -вершинный граф $G$ , можно преобразовать в экземпляр матроидной четности следующим образом. Постройте матроид мощения на $2n$ элементы, объединенные в пары так, что на пару вершин приходится одна пара элементов. Определить подмножество $S$ из этих элементов является независимым, если он удовлетворяет любому из следующих трех условий:

$S$ имеет меньше, чем $2k$ элементы.
$S$ имеет точно $2k$ элементов, но не является объединением $k$ пары элементов.
$S$ это союз $k$ пары элементов, образующие клику в $G$ .

Тогда существует решение проблемы четности матроида для этого матроида размером $2k$ , тогда и только тогда, когда $G$ имеет клику размера $k$ . Поскольку поиск клик заданного размера является NP-полным, отсюда следует, что определение того, имеет ли этот тип проблемы матричной четности решение размера $2k$ также NP-полна. ^{[ 13 ]}

Эта трансформация задачи не зависит каким-либо глубоким образом от структуры задачи о клике и будет работать для любой другой задачи определения размера. $k$ подмножества большего множества, удовлетворяющие вычислимому критерию. Применяя его к случайно переставленному графу, который содержит ровно одну клику размера $k$ , можно показать, что любой детерминированный или рандомизированный алгоритм проверки четности матроида, который обращается к своему матроиду только с помощью тестов независимости, должен выполнить экспоненциальное количество тестов. ^{[ 4 ]}

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Чунг, Хо Йи; Лау, Лап Чи; Люнг, Кай Ман (2014), «Алгебраические алгоритмы для задач четности линейных матроидов» (PDF) , Транзакции ACM в алгоритмах , 10 (3): 10:1–10:26, CiteSeerX 10.1.1.194.604 , doi : 10.1145/ 2601066 , МР 3233690 , С2КИД 894004
^ Перейти обратно: ^а ^б ^с ^д Лоулер, Юджин Л. (1976), «Глава 9: Проблема четности матроидов» , Комбинаторная оптимизация: сети и матроиды , Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 356–367, MR 0439106
^ Перейти обратно: ^а ^б ^с Ловас, Л. (1980), «Сопоставление матроидов и некоторые приложения», Журнал комбинаторной теории , серия B, 28 (2): 208–236, doi : 10.1016/0095-8956(80)90066-0 , MR 0572475
^ Перейти обратно: ^а ^б Дженсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi : 10.1137/0211014 , MR 0646772
^ Перейти обратно: ^а ^б Калинеску, Груя; Фернандес, Кристина Г.; Финклер, Ульрих; Карлофф, Ховард (1998), «Алгоритм лучшего приближения для поиска плоских подграфов», Journal of Algorithms , 27 (2): 269–302, CiteSeerX 10.1.1.47.4731 , doi : 10.1006/jagm.1997 , SMRID 2016 , 3976 8329680 .
^ Перейти обратно: ^а ^б Ферст, Меррик Л.; Гросс, Джонатан Л.; МакГеоч, Лайл А. (1988), «Нахождение вложения графа максимального рода», Журнал ACM , 35 (3): 523–534, doi : 10.1145/44483.44485 , MR 0963159 , S2CID 17991210
^ Перейти обратно: ^а ^б ^с Уэно, Шуичи; Кадзитани, Йоджи; Гото, Шинья (1988), «О проблеме неразделяющегося независимого множества и проблеме множества с обратной связью для графов, степень вершины которых не превышает трех», Труды Первой японской конференции по теории графов и приложениям (Хаконэ, 1986), Дискретная математика , 72 (1–3): 355–360, doi : 10.1016/0012-365X(88)90226-9 , MR 0975556
^ Перейти обратно: ^а ^б Ли, Джон; Свириденко Максим; Вондрак, Ян (2013), «Сопоставление матроидов: возможности локального поиска», SIAM Journal on Computing , 42 (1): 357–379, CiteSeerX 10.1.1.600.4878 , doi : 10.1137/11083232X , MR 3033132
^ Ле Галль, Франсуа (2014), «Степень тензоров и быстрое умножение матриц», Труды 39-го Международного симпозиума по символьным и алгебраическим вычислениям (ISSAC 2014) , Нью-Йорк: ACM, стр. 296–303, arXiv : 1401.7714 , doi : 10.1145/2608628.2608664 , ISBN 9781450325011 , МР 3239939 , S2CID 2597483
^ Гилен, Джеймс ; Ивата, Сатору (2005), «Сопоставление матроидов с помощью смешанных кососимметричных матриц», Combinatorica , 25 (2): 187–215, CiteSeerX 10.1.1.702.5431 , doi : 10.1007/s00493-005-0013-7 , MR 2127610 , S2CID 18576135
^ Габоу, Гарольд Н .; Столлманн, Маттиас (1985), «Эффективные алгоритмы пересечения и четности графических матроидов (расширенное резюме)», в книге Брауэр, Уилфрид (ред.), Автоматы, языки и программирование , конспекты лекций по информатике, том. 194, Берлин: Springer, стр. 210–220, doi : 10.1007/BFb0015746 , ISBN. 978-3-540-15650-5 , МР 0819256
^ Спекенмейер, Э. (1986), "Границы наборов вершин обратной связи неориентированных кубических графов", Алгебра, комбинаторика и логика в информатике, Vol. I, II (Дьёр, 1983) , Colloquia Mathematica Societatis János Bolyai, vol. 42, Амстердам: Северная Голландия, стр. 719–729, MR 0875903.
^ Сото, Хосе А. (2014), «Простой PTAS для взвешенного сопоставления матроидов на сильно базовых упорядочиваемых матроидах», Discrete Applied Mathematics , 164 (часть 2): 406–412, arXiv : 1102.3491 , doi : 10.1016/j.dam. 2012.10.019 , МР 3159127 , S2CID 17970404

[cll-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Чунг, Хо Йи; Лау, Лап Чи; Люнг, Кай Ман (2014), «Алгебраические алгоритмы для задач четности линейных матроидов» (PDF) , Транзакции ACM в алгоритмах , 10 (3): 10:1–10:26, CiteSeerX 10.1.1.194.604 , doi : 10.1145/ 2601066 , МР 3233690 , С2КИД 894004

[el-2] Перейти обратно: ^а ^б ^с ^д Лоулер, Юджин Л. (1976), «Глава 9: Проблема четности матроидов» , Комбинаторная оптимизация: сети и матроиды , Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 356–367, MR 0439106

[ll-3] Перейти обратно: ^а ^б ^с Ловас, Л. (1980), «Сопоставление матроидов и некоторые приложения», Журнал комбинаторной теории , серия B, 28 (2): 208–236, doi : 10.1016/0095-8956(80)90066-0 , MR 0572475

[jk-4] Перейти обратно: ^а ^б Дженсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi : 10.1137/0211014 , MR 0646772

[cffk-5] Перейти обратно: ^а ^б Калинеску, Груя; Фернандес, Кристина Г.; Финклер, Ульрих; Карлофф, Ховард (1998), «Алгоритм лучшего приближения для поиска плоских подграфов», Journal of Algorithms , 27 (2): 269–302, CiteSeerX 10.1.1.47.4731 , doi : 10.1006/jagm.1997 , SMRID 2016 , 3976 8329680 .

[fgm-6] Перейти обратно: ^а ^б Ферст, Меррик Л.; Гросс, Джонатан Л.; МакГеоч, Лайл А. (1988), «Нахождение вложения графа максимального рода», Журнал ACM , 35 (3): 523–534, doi : 10.1145/44483.44485 , MR 0963159 , S2CID 17991210

[ukg-7] Перейти обратно: ^а ^б ^с Уэно, Шуичи; Кадзитани, Йоджи; Гото, Шинья (1988), «О проблеме неразделяющегося независимого множества и проблеме множества с обратной связью для графов, степень вершины которых не превышает трех», Труды Первой японской конференции по теории графов и приложениям (Хаконэ, 1986), Дискретная математика , 72 (1–3): 355–360, doi : 10.1016/0012-365X(88)90226-9 , MR 0975556

[lsv-8] Перейти обратно: ^а ^б Ли, Джон; Свириденко Максим; Вондрак, Ян (2013), «Сопоставление матроидов: возможности локального поиска», SIAM Journal on Computing , 42 (1): 357–379, CiteSeerX 10.1.1.600.4878 , doi : 10.1137/11083232X , MR 3033132

[lg-9] Ле Галль, Франсуа (2014), «Степень тензоров и быстрое умножение матриц», Труды 39-го Международного симпозиума по символьным и алгебраическим вычислениям (ISSAC 2014) , Нью-Йорк: ACM, стр. 296–303, arXiv : 1401.7714 , doi : 10.1145/2608628.2608664 , ISBN 9781450325011 , МР 3239939 , S2CID 2597483

[gi-10] Гилен, Джеймс ; Ивата, Сатору (2005), «Сопоставление матроидов с помощью смешанных кососимметричных матриц», Combinatorica , 25 (2): 187–215, CiteSeerX 10.1.1.702.5431 , doi : 10.1007/s00493-005-0013-7 , MR 2127610 , S2CID 18576135

[gs-11] Габоу, Гарольд Н .; Столлманн, Маттиас (1985), «Эффективные алгоритмы пересечения и четности графических матроидов (расширенное резюме)», в книге Брауэр, Уилфрид (ред.), Автоматы, языки и программирование , конспекты лекций по информатике, том. 194, Берлин: Springer, стр. 210–220, doi : 10.1007/BFb0015746 , ISBN. 978-3-540-15650-5 , МР 0819256

[ds-12] Спекенмейер, Э. (1986), "Границы наборов вершин обратной связи неориентированных кубических графов", Алгебра, комбинаторика и логика в информатике, Vol. I, II (Дьёр, 1983) , Colloquia Mathematica Societatis János Bolyai, vol. 42, Амстердам: Северная Голландия, стр. 719–729, MR 0875903.

[js-13] Сото, Хосе А. (2014), «Простой PTAS для взвешенного сопоставления матроидов на сильно базовых упорядочиваемых матроидах», Discrete Applied Mathematics , 164 (часть 2): 406–412, arXiv : 1102.3491 , doi : 10.1016/j.dam. 2012.10.019 , МР 3159127 , S2CID 17970404

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]