В комбинаторной оптимизации , то матроид проблема четности является проблемой нахождения наибольшего независимого множества сопряженных элементов в матроиде . [1] Проблема была сформулирована Лоулером (1976) как общее обобщение сопоставления графов и пересечения матроидов . [1] [2] Это также известно как сопоставление полиматроидов или проблема сопоставления . [3]
Четность матроидов может быть решена за полиномиальное время для линейных матроидов . Однако это NP-сложно для некоторых компактно представленных матроидов и требует больше, чем полиномиальное количество шагов в модели оракула матроида . [1] [4]
Применение алгоритмов матроидных четности включает в себя нахождение больших плоских подграфов [5] и нахождение графы вложения из максимального рода . [6] Эти алгоритмы также могут использоваться для поиска связанных доминирующих множеств и множеств вершин обратной связи в графах максимальной степени три. [7]
Формулировка
Матроид может быть определен из конечного множества элементов и от понятия , что значит для подмножества элементов , чтобы быть независимым, с учетом следующих ограничений:
- Каждое подмножество независимого набора должно быть независимым.
- Если а также независимые множества, с , то существует элемент такой, что независим. [1]
Примеры матроидов включают линейные матроиды (в которых элементы являются векторами в векторном пространстве с линейной независимостью ), графические матроиды (в которых элементы являются ребрами в неориентированном графе , независимыми, если они не содержат цикла ) и разбиение матроиды (в которых элементы принадлежат семейству непересекающихся множеств и являются независимыми, если они содержат не более одного элемента в каждом наборе). Графические матроиды и матроиды-разбиения являются частными случаями линейных матроидов. [1]
В задаче четности матроида вход состоит из матроида вместе с парой его элементов, так что каждый элемент принадлежит одной паре. Цель состоит в том, чтобы найти как можно большее подмножество пар, чтобы объединение пар в выбранном подмножестве было независимым. [1] [2] Другой, казалось бы, более общий вариант, в котором допустимые пары образуют граф, а не имеют только одну пару на элемент, эквивалентен: элемент, входящий в более чем одну пару, может быть заменен несколькими копиями элемента, по одному на пару. [8]
Алгоритмы
Проблема четности матроидов для линейных матроидов может быть решена рандомизированным алгоритмом во времени., где - количество элементов матроида, - его ранг (размер наибольшего независимого множества), а- показатель степени в границах времени для быстрого умножения матриц . [1] В частности, используя алгоритм умножения матриц Ле Галля, [9] он может быть решен за время. Без использования быстрого матричного умножения задача линейного матроида на четность может быть решена за время. [1]
Эти алгоритмы основаны на формулировке задачи линейной алгеброй Гилена и Иваты (2005) . Предположим, что вход в задачу состоит из пара -мерные векторы (расположенные как векторы-столбцы в матрице размера ). Тогда количество пар в оптимальном решении равно
где является блок - диагональная матрица , чьи блоки подматрицы вида
для последовательности переменных . [10] Шварц-Zippel лемму можно использовать для тестирования , имеет ли эта матрица полный ранг или нет (то есть, есть ли решение размер или нет), присваивая случайные значения переменным и проверка того, имеет ли полученная матрица нулевой определитель . Применяя жадный алгоритм, который удаляет пары по одной, устанавливая их неопределенные значения равными нулю, пока матрица остается с полным рангом (поддерживая обратную матрицу с использованием формулы Шермана-Моррисона для проверки ранга после каждого удаления), можно найти решение всякий раз, когда этот тест показывает, что оно существует. Дополнительные методы распространяют этот алгоритм на случай, когда оптимальное решение задачи четности матроида имеет меньше, чемпары. [1]
Для графических матроидов известны более эффективные алгоритмы с наработкой на графиках с вершины и края. [11] Для простых графов , является , но для мультиграфов он может быть больше, поэтому также интересно иметь алгоритмы с меньшей зависимостью от и худшая зависимость от . В этих случаях также возможно решить задачу четности графического матроида за рандомизированное ожидаемое время., или вовремя когда каждая пара ребер образует путь. [1]
Хотя проблема четности матроидов является NP-сложной для произвольных матроидов, ее все же можно эффективно аппроксимировать. Простые алгоритмы локального поиска обеспечивают схему полиномиального приближения для этой задачи и находят решения, размер которых как часть оптимального размера решения сколь угодно близок к единице. Алгоритм начинается с пустого набора в качестве решения и неоднократно пытается увеличить размер решения на единицу, удаляя не более чем постоянное число.пар из решения и заменяя их другим набором еще одной парой. Когда такие ходы больше не возможны, результирующее решение возвращается как приближение к оптимальному решению. Для достижения коэффициента аппроксимации, достаточно выбрать быть приблизительно . [8]
Приложения
Многие другие задачи оптимизации могут быть сформулированы как задачи линейной четности матроидов и решены за полиномиальное время с использованием этой формулировки.
- Сопоставление графиков
- Соответствующий максимум в графе является подмножеством ребер, никаких два обмена конечной точки, то есть как можно больше. Его можно сформулировать как задачу четности матроида в матроиде разбиений, который имеет элемент для каждой инцидентности вершина-ребро в графе. В этом матроиде два элемента являются парными, если они являются двумя инцидентами для одного и того же ребра, что и друг друга. Подмножество элементов является независимым, если оно имеет не более одной инцидентности для каждой вершины графа. Пары элементов в решении задачи четности матроида для этого матроида - это инцидентности между ребрами в максимальном сопоставлении и их конечными точками. [2]
- Пересечение матроидов
- Пример задачи пересечения матроидов состоит из двух матроидов на одном и том же наборе элементов; цель состоит в том, чтобы найти подмножество элементов, которое является как можно большим и независимым в обоих матроидах. Чтобы сформулировать пересечение матроидов как проблему четности матроидов, постройте новый матроид, элементы которого представляют собой несвязное объединение двух копий заданных элементов, по одной для каждого входного матроида. В новом матроиде подмножество является независимым, если его ограничение на каждую из двух копий независимо в каждом из двух матроидов, соответственно. Соедините элементы нового матроида так, чтобы каждый элемент был соединен со своей копией. Пары элементов в решении проблемы четности матроидов для этого матроида являются двумя копиями каждого элемента в решении проблемы пересечения матроидов. [2]
- Большие плоские подграфы
В произвольном графе задача поиска наибольшего набора треугольников в данном графе без циклов, кроме выбранных треугольников, может быть сформулирована как задача четности матроида на графическом матроиде, элементы которого являются ребрами графа, с одним пара ребер на треугольник (дублирование ребер при необходимости, если они принадлежат более чем одному треугольнику). Пары элементов в решении задачи четности матроида для этого матроида - это два ребра в каждом треугольнике оптимального набора треугольников. Эту же проблему можно описать как задачу нахождения наибольшего ациклического по Берже под-гиперграфа 3-однородного гиперграфа . В гиперграфической версии задачи гиперребра - это треугольники данного графа. [3]
Кактуса график представляет собой график , в котором каждый из двух циклов имеют не более одной общей вершины. Как частный случай, графы, в которых каждый цикл представляет собой треугольник, обязательно являются графами кактусов. Самый большой треугольный кактус в данном графе затем можно найти, добавив дополнительные ребра из остовного дерева , без создания каких-либо новых циклов, так что результирующий подграф имеет те же компоненты связности, что и исходный граф. Графы кактусов автоматически являются планарными графами , и проблема поиска треугольных графов кактусов формирует основу для наиболее известного алгоритма приближения к проблеме поиска самого большого плоского подграфа данного графа, что является важным шагом в планаризации . Самый большой треугольный кактус всегда имеет как минимум 4/9 числа ребер самого большого плоского подграфа, что улучшает коэффициент приближения 1/3, полученный при использовании произвольного остовного дерева. [5]
- Комбинаторная жесткость
- Каркас из жестких стержней в евклидовой плоскости , соединенных на концах гибкими соединениями, может быть зафиксирован в одном положении на плоскости, прикрепив некоторые из его сочленений к точкам плоскости. Минимальное количество стыков, которое необходимо закрепить штифтом для фиксации каркаса, называется его номером штифта. Его можно вычислить из решения связанной с ним проблемы четности матроидов. [3]
- Вложения максимального рода
Сотовое вложение данного графа на поверхность максимально возможного рода может быть получено из дерева Xuong графа. Это остовное дерево, обладающее тем свойством, что в подграфе ребер, не входящих в дерево, количество связанных компонентов с нечетным числом ребер как можно меньше.
Чтобы сформулировать задачу поиска дерева Xuong как задачу четности матроидов, сначала разделите каждое ребро данного графа в путь, длина которого равна количеству других ребер, инцидентных . Затем соедините ребра разбитого графа так, чтобы каждая пара ребер в исходном графе была представлена одной парой ребер в разбитом графе, а каждое ребро в разбитом графе было спарено ровно один раз. Решите задачу четности матроида с парными ребрами разделенного графа, используя его копографический матроид (линейный матроид, в котором подмножество ребер является независимым, если его удаление не разделяет граф). Любое остовное дерево исходного графа, которое избегает ребер, используемых в решении четности матроида, обязательно является деревом Xuong. [6]
- Связанное господство
- Связное множество доминирующего в графе является подмножеством вершин, подграф соединен, смежно со всеми остальными вершинами. Найти наименьшее связное доминирующее множество в произвольных графах NP-сложно, но для графов максимальной степени три его можно найти за полиномиальное время. В кубическом графе можно заменить каждую вершину двухреберным путем, соединенным с концами трех его конечных точек, и сформулировать задачу четности матроида на парах ребер, сгенерированных таким образом, с использованием графического матроида расширенного графа. Вершины, пути которых не используются в решении, образуют минимальное связное доминирующее множество. В графе максимальной степени три некоторые простые дополнительные преобразования сводят задачу к кубическому графу. [7]
- Набор вершин обратной связи
- Множество вершин обратной связи в графе - это подмножество вершин, которое касается всех циклов. В кубических графах существует линейное уравнение, связывающее количество вершин, цикломатическое число , количество связанных компонентов, размер минимального связного доминирующего множества и размер минимального набора вершин обратной связи. [12] Отсюда следует, что та же проблема четности матроидов, которая использовалась для поиска связных доминирующих множеств, может также использоваться для поиска множеств вершин обратной связи в графах максимальной степени три. [7]
Твердость
Проблема клики , найти-вершинный полный подграф в заданном-вершинный граф , можно преобразовать в пример четности матроидов следующим образом. Постройте матроид для мощения наэлементы, сгруппированные так, чтобы на пару вершин приходилась одна пара элементов. Определить подмножество этих элементов будет независимым, если он удовлетворяет любому из следующих трех условий:
- имеет меньше чем элементы.
- точно элементов, но не является объединением пары элементов.
- это союз пары элементов, которые образуют клику в .
Тогда есть решение проблемы четности матроида для этого матроида размером , если и только если имеет размер группы . Поскольку поиск клик заданного размера является NP-полным, отсюда следует, что определение того, имеет ли этот тип матричной проблемы четности решение размератакже NP-полна. [13]
Это преобразование задачи не зависит от структуры проблемы клики каким-либо образом и будет работать для любой другой задачи определения размера.подмножества большего набора, удовлетворяющие вычислимому тесту. Применяя его к случайно перестановочному графу, который содержит ровно одну клику размера, можно показать, что любой детерминированный или рандомизированный алгоритм проверки четности матроидов, который обращается к своему матроиду только с помощью тестов независимости, должен выполнять экспоненциальное количество тестов. [4]
Рекомендации
- ^ a b c d e f g h i j Cheung, Ho Yee; Лау, Лап Чи; Леунг, Кай Ман (2014), «Алгебраические алгоритмы для линейных задач четности матроидов» (PDF) , Транзакции ACM по алгоритмам , 10 (3): 10: 1–10: 26, CiteSeerX 10.1.1.194.604 , DOI : 10.1145 / 2601066 , Руководство 3233690 , S2CID 894004
- ^ а б в г Лоулер, Юджин Л. (1976), «Глава 9: Проблема четности матроидов» , Комбинаторная оптимизация: сети и матроиды , Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 356–367, MR 0439106 CS1 maint: обескураженный параметр ( ссылка )
- ^ а б в Ловаса, Л. (1980), "матроида Совпадение и некоторые приложения", Журнал комбинаторной теории , Series B, 28 (2): 208-236, DOI : 10,1016 / 0095-8956 (80) 90066-0 , МР 0572475 CS1 maint: обескураженный параметр ( ссылка )
- ^ а б Jensen, Per M .; Корте, Бернхард (1982), "Сложность алгоритмов матроидных собственности", SIAM журнал по вычислениям , 11 (1): 184-190, DOI : 10,1137 / 0211014 , МР 0646772
- ^ а б Кэлинеску, Груя; Fernandes, Cristina G .; Финклер, Ульрих; Карлофф, Говард (1998), "Лучший алгоритм аппроксимации для нахождения плоских подграфов", журнал алгоритмов , 27 (2): 269-302, CiteSeerX 10.1.1.47.4731 , DOI : 10,1006 / jagm.1997.0920 , MR 1622397 , S2CID 8329680.
- ^ а б Furst, Merrick L .; Гросс, Джонатан Л .; McGeoch, Лайл А. (1988), "Нахождение максимальной род графа вложение", Журнал ACM , 35 (3): 523-534, DOI : 10,1145 / 44483,44485 , МР 0963159 , S2CID 17991210
- ^ а б в Уэно, Шуичи; Кадзитани, Йоджи; Гото, Shin'ya (1988), «О nonseparating независимого множества и множество обратной задачи для графиков без степени вершин , превышающих три», Труды Первой японской конференции по теории и приложениям Graph (Хаконэ, 1986), дискретная математика , 72 (1–3): 355–360, DOI : 10.1016 / 0012-365X (88) 90226-9 , MR 0975556
- ^ а б Ли, Джон; Свириденко, Максим; Вондрак, Ян (2013), «Соответствие Matroid: возможности локального поиска», 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, 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 , МР 2127610 , S2CID 18576135
- ^ Габоу, Гарольд Н .; Столлманн, Маттиас (1985), «Эффективные алгоритмы для пересечения графических матроидов и четности (расширенная аннотация)», Брауэр, Вильфрид (редактор), 12-й Международный коллоквиум по автоматам, языкам и программированию (ICALP), Нафплион, Греция, июль 15-19, 1985 , Lecture Notes в области компьютерных наук, 194 , Berlin: Springer, С. 210-220,. DOI : 10.1007 / BFb0015746 , ISBN 978-3-540-15650-5, MR 0819256
- ^ Speckenmeyer, E. (1986), "Границы наборов вершин обратной связи неориентированных кубических графов", Алгебра, комбинаторика и логика в компьютерных науках, Vol. 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