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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

где — блочно-диагональная матрица , блоки которой являются подматрицами вида $Т$ $2\times 2$

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

Связанное господство

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

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

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

Твёрдость

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

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

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

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

Ссылки

^ abcdefghij Cheung, Ho Yee; Lau, Lap Chi; Leung, Kai Man (2014), «Алгебраические алгоритмы для линейных задач четности матроидов» (PDF) , ACM Transactions on Algorithms , 10 (3): 10:1–10:26, CiteSeerX 10.1.1.194.604 , doi :10.1145/2601066, MR 3233690, S2CID 894004
^ abcd Лоулер, Юджин Л. (1976), «Глава 9: Проблема четности матроидов», Комбинаторная оптимизация: сети и матроиды , Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 356–367, MR 0439106
^ abc Lovász, L. (1980), «Соответствие матроидов и некоторые приложения», Журнал комбинаторной теории , Серия B, 28 (2): 208–236, doi : 10.1016/0095-8956(80)90066-0 , MR 0572475
^ ab Jensen, Per M.; Korte, Bernhard (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.0920, MR 1622397, S2CID 8329680 .
^ ab Furst, Merrick L.; Gross, Jonathan L.; McGeoch, Lyle A. (1988), "Finding a maximum-genus graph imbedding", Journal of the ACM , 35 (3): 523–534, doi : 10.1145/44483.44485 , MR 0963159, S2CID 17991210
^ abc Уэно, Шуичи; Кадзитани, Ёдзи; Гото, Синъя (1988), «О проблеме неразделяющего независимого множества и проблеме множества обратной связи для графов, у которых степень вершины не превышает трёх», Труды Первой японской конференции по теории графов и её приложениям (Хаконэ, 1986), Дискретная математика , 72 (1–3): 355–360, doi : 10.1016/0012-365X(88)90226-9 , MR 0975556
^ ab Ли, Джон; Свириденко, Максим; Вондрак, Ян (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, MR 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), «Эффективные алгоритмы для графического пересечения матроидов и четности (расширенная аннотация)», в Brauer, Wilfried (ред.), Automata, Languages and Programming , Lecture Notes in Computer Science, т. 194, Берлин: Springer, стр. 210–220, doi :10.1007/BFb0015746, ISBN 978-3-540-15650-5, МР 0819256
^ Speckenmeyer, E. (1986), "Границы множеств вершин обратной связи неориентированных кубических графов", Алгебра, комбинаторика и логика в информатике, т. I, II (Дьёр, 1983) , Colloquia Mathematica Societatis János Bolyai, т. 42, Амстердам: Северная Голландия, стр. 719–729, MR 0875903
^ Сото, Хосе А. (2014), «Простая PTAS для взвешенного сопоставления матроидов на строго базовых упорядочиваемых матроидах», Дискретная прикладная математика , 164 (часть 2): 406–412, arXiv : 1102.3491 , doi : 10.1016/j.dam.2012.10.019, MR 3159127, S2CID 17970404