Двумерность

Теория двумерности характеризует широкий спектр задач на графах ( двумерных ), которые допускают эффективные приближенные решения с фиксированным параметром или ядром в широком диапазоне графов. Эти классы графов включают плоские графы , графы-карты, графы ограниченного рода и графы, исключающие любой фиксированный минор. В частности, теория двумерности основывается на минорных графов теории Робертсона и Сеймура путем расширения математических результатов и создания новых алгоритмических инструментов. Теория была представлена в работах Демена , Фомина , Хаджиагайи и Тиликоса. ^[1] за что авторы получили премию Нероде в 2015 году.

Определение

проблема Параметризованная $\Pi$ является подмножеством $\Gamma ^{*}\times \mathbb {N}$ для некоторого конечного алфавита $\Gamma$ . Экземпляр параметризованной задачи состоит из (x,k) , где k называется параметром.

Параметризованная проблема $\Pi$ является минорно-двумерным, если

Для любой пары графов $H,G$ , такой, что $H$ является несовершеннолетним из $G$ и целое число $k$ , $(G,k)\in \Pi$ получается, что $(H,k)\in \Pi$ . Другими словами, стягивание или удаление ребра в графе $G$ невозможно увеличить параметр; и
есть $\delta >0$ такой, что для каждого $(r\times r)$ -сетка $R$ , $(R,k)\not \in \Pi$ для каждого $k\leq \delta r^{2}$ . Другими словами, ценность решения на $R$ должно быть по крайней мере $\delta r^{2}$ .

Примерами второстепенных двумерных задач являются параметризованные версии вершинного покрытия , набора вершин обратной связи , минимального максимального сопоставления и самого длинного пути .

Позволять $\Gamma _{r}$ быть графиком, полученным из $(r\times r)$ -сетка потриангуляция внутренних граней так, чтобы все внутренние вершины имели степень 6,а затем один угол второй степени, соединенный ребрами со всеми вершинамивнешнего лица.Параметризованная проблема $\Pi$ является двумерным сжиманием, если

Для любой пары графов $H,G$ , такой, что $H$ представляет собой сокращение $G$ и целое число $k$ , $(G,k)\in \Pi$ получается, что $(H,k)\in \Pi$ . Другими словами, сужение ребра в графе $G$ невозможно увеличить параметр; и
есть $\delta >0$ такой, что $(\Gamma _{r},k)\not \in \Pi$ для каждого $k\leq \delta r^{2}$ .

Примерами двумерных задач сжатия являются доминирующее множество , связное доминирующее множество , остовное дерево с максимальными листьями и доминирующее множество ребер .

Теоремы об исключенной сетке

Все алгоритмические применения двумерности основаны на следующем комбинаторном свойстве: либо ширина дерева графа мала, либо граф содержит большую сетку в качестве минора или сжатия. Точнее,

Существует функция f такая, что каждый граф G, за исключением графа с фиксированными h -вершинами в качестве минора и древовидной ширины не менее f(h)r, содержит (rxr) -сетку в качестве минора. ^[2]
Существует функция g такая, что каждый граф G, фиксированной вершиной h -вершины за исключением графа с в качестве минора и древовидной ширины не менее g(h) r, может быть стянут по ребру до $\Gamma _{r}$ . ^[3]

Теорема Халина о сетке - это аналогичная теорема об исключенной сетке для бесконечных графов. ^[4]

Субэкспоненциальные параметризованные алгоритмы

Позволять $\Pi$ — минорная двумерная задача, такая, что для любого графа G, за исключением некоторого фиксированного графа в качестве минора и древовидной ширины не более t , решение о том, является ли $(G,k)\in \Pi$ можно сделать вовремя $2^{O(t)}\cdot |G|^{O(1)}$ . Затем для каждого графа G, исключая некоторый фиксированный граф как минор, решая, является ли $(G,k)\in \Pi$ можно сделать вовремя $2^{O({\sqrt {k}})}\cdot |G|^{O(1)}$ . Аналогично, для двумерных задач сжатия, для графа G, исключающего некоторый граф с фиксированной вершиной в качестве минора, включение $(G,k)\in \Pi$ можно решить со временем $2^{O({\sqrt {k}})}\cdot |G|^{O(1)}$ .

Таким образом, многие двумерные задачи, такие как покрытие вершин, доминирующий набор, k-путь, разрешимы за время. $2^{O({\sqrt {k}})}\cdot |G|^{O(1)}$ на графах, исключая некоторый фиксированный граф как минор.

Схемы аппроксимации полиномиального времени

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

В частности, с помощью двумерности было показано, что множество вершин обратной связи , покрытие вершин , связное покрытие вершин, упаковка циклов, набор ромбовидных попаданий, максимальный индуцированный лес, максимальный индуцированный двудольный подграф и максимальный индуцированный планарный подграф допускают EPTAS на H- графы без миноров. Доминирующее множество ребер, доминирующее множество , r-доминирующее множество, связное доминирующее множество, r-разбросанное множество, минимальное максимальное паросочетание, независимый набор , максимальное остовное дерево полной степени, максимальное индуцированное подграф не более d-степени, максимальное внутреннее остовное дерево , индуцированное паросочетание , упаковка треугольников, частичное r-доминантное множество и частичное вершинное покрытие допускают EPTAS на графах без вершинных миноров.

Кернелизация

Говорят, что параметризованная задача с параметром k допускает линейное вершинное ядро, если существует полиномиальное сокращение времени, называемое алгоритмом кернеризации , которое отображает входной экземпляр в эквивалентный экземпляр с не более чем O (k) вершинами.

Каждая второстепенная двумерная проблема $\Pi$ с дополнительными свойствами, а именно свойством отделимости и конечным целочисленным индексом, имеет линейное вершинное ядро на графах, исключающее некоторый фиксированный граф в качестве минора. Аналогично, каждая двумерная задача сжатия $\Pi$ со свойством разделения и с конечным целочисленным индексом, имеет линейное вершинное ядро на графах, исключающее некоторый граф с фиксированной вершиной в качестве минора. ^[7]

Примечания

Ссылки

Демейн, Эрик Д.; Фомин Федор Владимирович; Хаджиагайи, Мохаммад Таги; Тиликос, Димитриос М. (2005), «Субэкспоненциальные параметризованные алгоритмы на графах ограниченного рода и H -минорных графах», J. ACM , 52 (6): 866–893, arXiv : 1104.2230 , doi : 10.1145/1101821.1101823 , S2CID 6238832 .
Демейн, Эрик Д.; Фомин Федор Владимирович; Хаджиагайи, Мохаммад Таги; Тиликос, Димитриос М. (2004), «Двумерные параметры и ширина локального дерева», SIAM Journal on Discrete Mathematics , 18 (3): 501–511, CiteSeerX 10.1.1.81.9021 , doi : 10.1137/S0895480103433410 .
Демейн, Эрик Д.; Хаджиагайи, Мохаммад Таги (2005), «Двумерность: новые связи между алгоритмами FPT и PTAS», 16-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2005) , стр. 590–601 .
Демейн, Эрик Д.; Хаджиагайи, Мохаммад Таги (2008a), «Линейность миноров сетки по ширине дерева с приложениями через двумерность», Combinatorica , 28 (1): 19–36, doi : 10.1007/s00493-008-2140-4 , S2CID 16520181 .
Демейн, Эрик Д.; Хаджиагайи, Мохаммад Таги (2008b), «Теория двумерности и ее алгоритмические приложения», The Computer Journal , 51 (3): 292–302, doi : 10.1093/comjnl/bxm033 , hdl : 1721.1/33090 .
Дистель, Р. (2004), «Краткое доказательство теоремы Халина о сетке», Статьи математического семинара Гамбургского университета , 74 : 237–242, doi : 10.1007/BF02941538 , MR 2112834 , S2CID 124603912 .
Фомин Федор Владимирович; Головач Петр А.; Тиликос, Димитриос М. (2009), «Двумерность сокращения: точная картина», 17-й ежегодный европейский симпозиум по алгоритмам (ESA 2009) , Конспекты лекций по информатике, том. 5757, стр. 706–717, номер doi : 10.1007/978-3-642-04128-0_63 , ISBN. 978-3-642-04127-3 .
Фомин Федор Владимирович; Локштанов Даниил; Раман, Венкатеш; Саураб, Сакет (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

[dfht05-1] Демейн и др. (2005)

[dh06-2] Демейн и Хаджиагайи (2008a) ^{[ нужны разъяснения ]}

[fgt09-3] Фомин, Головач и Тиликос (2009)

[4] Дистель (2004)

[flrs10-5] Fomin et al. (2011)

[dh05-6] Демейн и Хаджиагайи (2005)

[flst10-7] Fomin et al. (2010)

[1]

[2]

[3]

[4]

[5]

[6]

[7]