Двумерность - Википедия - Bidimensionality
Двумерность теория характеризует широкий круг задач графов (двумерный), которые допускают эффективные приближенные решения с фиксированными параметрами или ядра в широком диапазоне графиков. Эти классы графов включают планарные графы, карта графиков, ограниченный род графики и графики без фиксированного второстепенного. В частности, теория двумерности опирается на граф минор теория Робертсон и Сеймур за счет расширения математических результатов и создания новых алгоритмических инструментов. Теория была введена в работе Demaine, Фомин, Hajiaghayi, и Тиликос,[1] за что авторы получили Приз Нероде в 2015 году.
Определение
А параметризованная задача это подмножество для некоторого конечного алфавита . Пример параметризованной задачи состоит из (х, к), куда k называется параметром.
Параметризованная проблема является малоразмерный если
- Для любой пары графиков , так что является несовершеннолетним из и целое число , дает, что . Другими словами, сжатие или удаление ребра в графе не может увеличить параметр; и
- есть так что для каждого -сетка , для каждого . Другими словами, значение решения на должно быть как минимум .
Примерами второстепенных двумерных задач являются параметризованные версии крышка вершины, набор вершин обратной связи, минимальное максимальное соответствие, и самый длинный путь.
Позволять - граф, полученный из -сетка путем триангуляции внутренних граней таким образом, что все внутренние вершины имеют степень 6, а затем один угол степени два, соединенный ребрами со всеми вершинами внешней грани. является сжатие-двумерный если
- Для любой пары графиков , так что является сокращением и целое число , дает, что . Другими словами, сжатие ребра в графе не может увеличить параметр; и
- есть такой, что для каждого .
Примеры двумерных задач сжатия: доминирующий набор, связное доминирующее множество, остовное дерево с максимальным числом листьев и набор с доминирующим краем.
Исключенные сеточные теоремы
Все алгоритмические приложения двумерности основаны на следующем комбинаторном свойстве: либо ширина дерева графа является маленьким, или граф содержит большую сетку в качестве второстепенной или сжатой. Точнее,
- Есть функция ж такой, что каждый граф грамм за исключением фиксированного час-вершинный граф как незначительный и шириной не менее f (h) r содержит (г х г)-сетка как несовершеннолетняя.[2]
- Есть функция грамм такой, что каждый граф грамм за исключением фиксированного час-вертекс вершина графика как несовершеннолетний и шириной не менее г (ч) г может быть сокращено до .[3]
Сеточная теорема Халина аналогичная теорема об исключенной сетке для бесконечных графов.[4]
Субэкспоненциальные параметризованные алгоритмы
Позволять - двумерная второстепенная задача, такая что для любого графа грамм за исключением некоторого фиксированного графа в качестве второстепенного и максимальной ширины дерева т, решая, можно сделать вовремя . Тогда для каждого графа грамм исключая некоторый фиксированный граф как второстепенный, решая, можно сделать вовремя . Точно так же для двумерных задач сжатия граф грамм за исключением некоторых фиксированных вершина графика как несовершеннолетний, включение можно решить вовремя .
Таким образом, многие двумерные задачи, такие как Vertex Cover, Dominating Set, k-Path, разрешимы во времени. на графах, за исключением некоторого фиксированного графа в качестве второстепенного.
Схемы аппроксимации полиномиальным временем
Теория двумерности была использована для получения схемы полиномиальной аппроксимации для многих двумерных задач. Если второстепенная (сжатая) двумерная задача имеет несколько дополнительных свойств [5][6] тогда задача ставит эффективные схемы аппроксимации за полиномиальное время на (вершинных) графах без миноров.
В частности, с помощью двумерности было показано, что набор вершин обратной связи, крышка вершины, связное покрытие вершин, упаковка циклов, набор совпадений ромбов, максимальный индуцированный лес, максимальный индуцированный двудольный подграф и максимальный индуцированный планарный подграф допускают EPTAS на H-минорных графах. Край доминирующий набор, доминирующий набор, r-доминирующее множество, связное доминирующее множество, r-рассеянное множество, минимальное максимальное соответствие, независимый набор, максимальное остовное дерево полной степени, максимально индуцированный подграф не более d-степени, максимальное внутреннее связующее дерево, индуцированное соответствие, упаковка треугольников, частичное r-доминирующее множество и частичное покрытие вершин допускают EPTAS на графах без апекс-миноров.
Кернелизация
Параметризованная задача с параметром k называется допускающим линейное вершинное ядро, если существует полиномиальное сокращение времени, называемое ядро алгоритм, который сопоставляет входной экземпляр эквивалентному экземпляру с не более чем Ok) вершины.
Каждая второстепенная двумерная проблема с дополнительными свойствами, а именно со свойством разделенности и с конечным целочисленным индексом, имеет линейное вершинное ядро на графах, исключая некоторый фиксированный граф в качестве второстепенного. Точно так же каждая двумерная задача сжатия со свойством отделимости и с конечным целым индексом имеет линейное вершинное ядро на графах, за исключением некоторых фиксированных вершина графика как несовершеннолетний.[7]
Примечания
Рекомендации
- Demaine, Erik D .; Фомин, Федор В .; Хаджиагайи, Мохаммад Таги; Тиликос, Димитриос М. (2005), "Субэкспоненциальные параметризованные алгоритмы на графах ограниченного рода и ЧАС-без минорных графиков », J. ACM, 52 (6): 866–893, arXiv:1104.2230, Дои:10.1145/1101821.1101823, S2CID 6238832.
- Demaine, Erik D .; Фомин, Федор В .; Хаджиагайи, Мохаммад Таги; Тиликос, Димитриос М. (2004), «Двумерные параметры и локальная ширина деревьев», Журнал SIAM по дискретной математике, 18 (3): 501–511, CiteSeerX 10.1.1.81.9021, Дои:10.1137 / S0895480103433410.
- Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2005), "Двумерность: новые связи между алгоритмами FPT и PTAS", 16-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2005), стр. 590–601.
- Demaine, Erik D .; Хаджиагайи, Мохаммад Таги (2008), «Линейность миноров сетки в ширине дерева с приложениями через двумерность», Комбинаторика, 28 (1): 19–36, Дои:10.1007 / s00493-008-2140-4, S2CID 16520181.
- Demaine, Erik D .; Хаджиагайи, Мохаммад Таги (2008), "Теория двумерности и ее алгоритмические приложения", Компьютерный журнал, 51 (3): 332–337, Дои:10.1093 / comjnl / bxm033, HDL:1721.1/33090.
- Дистель, Р. (2004), "Краткое доказательство сеточной теоремы Халина", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 74: 237–242, Дои:10.1007 / BF02941538, МИСТЕР 2112834, S2CID 124603912.
- Фомин, Федор В .; Головач, Петр А .; Тиликос, Димитриос М. (2009), «Двумерность сокращения: точное изображение», 17-й ежегодный европейский симпозиум по алгоритмам (ESA 2009), Конспект лекций по информатике, 5757, стр. 706–717, Дои:10.1007/978-3-642-04128-0_63.
- Фомин, Федор В .; Локштанов Даниил; Раман, Венкатеш; Саураб, Сакет (2011), «Двумерность и EPTAS», Proc. 22-й симпозиум ACM / SIAM по дискретным алгоритмам (SODA 2011), стр. 748–759, arXiv:1005.5449, Bibcode:2010arXiv1005.5449F.
- Фомин, Федор В .; Локштанов Даниил; Саураб, Сакет; Тиликос, Димитриос М. (2010), «Двумерность и ядра», 21-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2010), стр. 503–510.
дальнейшее чтение
- Циган, Марек; Фомин, Федор В .; Ковалик, Лукаш; Локштанов Даниил; Маркс, Даниил; Пилипчук, Марцин; Пилипчук, Михал; Саураб, Сакет (2015), «Глава 7», Параметризованные алгоритмы, Springer, стр. 612, г. ISBN 978-3-319-21274-6
- Фомин, Федор В .; Локштанов Даниил; Саураб, Сакет; Зехави, Мейрав (2019), «Глава 15», Кернелизация: теория параметризованной предварительной обработки, Cambridge University Press, стр. 528, г. Дои:10.1017/9781107415157, ISBN 978-1107057760