Теория двумерности характеризует широкий спектр задач графов ( двумерных ), которые допускают эффективные приближенные решения с фиксированными параметрами или ядра в широком диапазоне графов. Эти классы графов включают плоские графы , графы карт, графы ограниченного рода и графы, исключая любые фиксированные второстепенные. В частности, теория двумерности основывается на теории минорных графов Робертсона и Сеймура , расширяя математические результаты и создавая новые алгоритмические инструменты. Теория была представлена в работах Демейна , Фомина , Хаджиагайи и Тиликоса [1].за что авторы получили Премию Нероде в 2015 году.
Определение
Параметризованная проблема это подмножество для некоторого конечного алфавита . Экземпляр параметризованной задачи состоит из (x, k) , где k называется параметром.
Параметризованная проблема является второстепенным двумерным, если
- Для любой пары графиков , так что является несовершеннолетним и целое число , дает, что . Другими словами, сжатие или удаление ребра в графене может увеличить параметр; а также
- Там есть такой, что для каждого -сетка , для каждого . Другими словами, значение решения на должно быть как минимум .
Примерами второстепенных двумерных задач являются параметризованные версии вершинного покрытия , набор вершин обратной связи , минимальное максимальное соответствие и самый длинный путь .
Позволять - график, полученный из -сетка путем триангуляции внутренних граней таким образом, чтобы все внутренние вершины имели степень 6, а затем один угол степени два, соединенный ребрами со всеми вершинами внешней грани. Параметризованная проблемаявляется сжато-двумерным, если
- Для любой пары графиков , так что является сокращением и целое число , дает, что . Другими словами, сжатие ребра в графене может увеличить параметр; а также
- Там есть такой, что для каждого .
Примерами двумерных задач сжатия являются доминирующее множество , связное доминирующее множество , остовное дерево с максимальным листом и множество с преобладанием ребер .
Исключенные сеточные теоремы
Все алгоритмические приложения двумерности основаны на следующем комбинаторном свойстве: либо ширина дерева графа мала, либо граф содержит большую сетку в качестве второстепенной или сжатой. Точнее,
- Существует функция f такая, что каждый граф G, за исключением графа с фиксированной h- вершиной в качестве второстепенного и с шириной дерева не менее f (h) r, содержит (rxr) -сетку в качестве второстепенного. [2]
- Существует функция g такая, что любой граф G, за исключением графа с вершиной с фиксированной h- вершиной как минор и шириной дерева не менее g (h) r, может быть сжат до. [3]
Теорема Халина о сетке является аналогичной теоремой об исключенной сетке для бесконечных графов. [4]
Субэкспоненциальные параметризованные алгоритмы
Позволять быть второстепенной двумерной задачей, такой что для любого графа G, исключая некоторый фиксированный граф как второстепенный и имеющий ширину дерева не более t , определение того, является ли можно сделать вовремя . Затем для каждого графа G, исключая некоторый фиксированный граф в качестве второстепенного, решая, будет ли можно сделать вовремя . Аналогичным образом, для двумерных задач сжатия, для графа G, исключая некоторый фиксированный вершинный граф в качестве второстепенного, включение можно решить вовремя .
Таким образом, многие двумерные задачи, такие как Vertex Cover, Dominating Set, k-Path, разрешимы во времени. на графах за исключением некоторого фиксированного графа в качестве второстепенного.
Схемы аппроксимации полиномиальным временем
Теория двумерности использовалась для получения схем аппроксимации за полиномиальное время для многих двумерных задач. Если второстепенная (сжатая) двумерная задача имеет несколько дополнительных свойств [5] [6], то задача представляет собой эффективные схемы аппроксимации за полиномиальное время на (вершинах) минорных графов.
В частности, с помощью двумерности было показано, что множество вершин обратной связи , покрытие вершин , связное покрытие вершин, упаковка циклов, набор совпадений ромба, максимальный индуцированный лес, максимальный индуцированный двудольный подграф и максимальный индуцированный плоский подграф допускают EPTAS на H- графы без миноров. Множество с преобладанием ребер, доминирующее множество , r-доминирующее множество, связное доминирующее множество, r-рассеянное множество, минимальное максимальное соответствие, независимый набор , максимальное остовное дерево полной степени, максимальное индуцированное подграф не более d-степени, максимальное внутреннее остовное дерево , индуцированное сопоставление , упаковка треугольников, частичное r-доминирующее множество и частичное покрытие вершин допускают EPTAS на графах без минорных вершин.
Кернелизация
Говорят, что параметризованная задача с параметром k допускает линейное вершинное ядро, если существует полиномиальное сокращение времени, называемое алгоритмом ядра , который отображает входной экземпляр в эквивалентный экземпляр с не более чем O (k) вершинами.
Каждая второстепенная двумерная проблема с дополнительными свойствами, а именно со свойством разделенности и с конечным целочисленным индексом, имеет линейное вершинное ядро на графах, за исключением некоторого фиксированного графа в качестве второстепенного. Точно так же каждая двумерная задача сжатиясо свойством разделения и с конечным целочисленным индексом имеет линейное вершинное ядро на графах, за исключением некоторого фиксированного вершинного графа в качестве второстепенного. [7]
Заметки
- ^ Demaine et al. (2005)
- ^ Demaine & Hajiaghayi (2008) ошибка harvtxt: несколько целей (2 ×): CITEREFDemaineHajiaghayi2008 ( справка )
- ↑ Фомин, Головач и Тиликос (2009)
- ^ Дистель (2004)
- ^ Фомин и др. (2011)
- ^ Demaine & Hajiaghayi (2005)
- ^ Фомин и др. (2010)
Рекомендации
- Demaine, Erik D .; Фомин, Федор В .; Хаджиагайи, Мохаммад Таги; Тиликос, Димитриос М. (2005), «Субэкспоненциальные параметризованные алгоритмы на графах ограниченного рода и графах без H- миноров», J. ACM , 52 (6): 866–893, arXiv : 1104.2230 , doi : 10.1145 / 1101821.1101823 , S2CID 6238832.
- Demaine, Erik D .; Фомин, Федор В .; Хаджиагайи, Мохаммад Таги; Thilikos, Димитриос М. (2004), "двумерный параметры и локальная древесная ширина", SIAM журнал по дискретной математике , 18 (3): 501-511, CiteSeerX 10.1.1.81.9021 , DOI : 10,1137 / S0895480103433410.
- Demaine, Erik D .; Хаджиагайи, Мохаммад Таги (2005), «Двумерность: новые связи между алгоритмами FPT и PTAS», 16-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2005) , стр. 590–601.
- Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2008), "Линейность сетки несовершеннолетних древесная ширина с приложениями через bidimensionality", Combinatorica , 28 (1): 19-36, DOI : 10.1007 / s00493-008-2140-4 , S2CID 16520181.
- Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2008), "Теория bidimensionality и ее алгоритмические приложения", Компьютерный журнал , 51 (3): 332-337, DOI : 10,1093 / comjnl / bxm033 , ЛВП : 1721,1 / 33090.
- Diestel, R. (2004), "Короткое доказательство теоремы Халин в сетке", Abhandlungen AUS DEM Mathematischen Семинаре дер Universität Hamburg , 74 : 237-242, DOI : 10.1007 / BF02941538 , MR 2112834 , S2CID 124603912.
- Фомин, Федор В .; Головач, Петр А .; Thilikos, Димитриос M. (2009), "Сужение Bidimensionality: Точная Picture", семнадцатый ежегодный Европейский симпозиум по алгоритмам (ESA 2009) , Lecture Notes в области компьютерных наук, 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, p. 612, ISBN 978-3-319-21274-6
- Фомин, Федор В .; Локштанов Даниил; Саураб, Сакет; Зехави, Мейрав (2019), «Глава 15», Кернелизация: теория параметризованной предварительной обработки , Cambridge University Press, стр. 528, DOI : 10,1017 / 9781107415157 , ISBN 978-1107057760