1294
правки
Двумерность: различия между версиями
Перейти к навигации
Перейти к поиску
→Литература
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Теория двумерности включает обобщенные техники разработки эффект…») |
KVN (обсуждение | вклад) |
||
| (не показаны 23 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
Теория двумерности включает обобщенные техники разработки эффективных алгоритмов с фиксированными параметрами и алгоритмов | Теория двумерности включает обобщенные техники разработки эффективных алгоритмов с фиксированными параметрами и аппроксимационных алгоритмов для широкого круга NP-полных графовых задач на широком круге графов. Эта теория применяется к графовым задачам, которые являются «двумерными» в следующем смысле: (1) значение решения для графа, представленного в виде решетки <math>k \times k \;</math>, и подобных ему графов растет вместе с k, обычно как <math>\Omega (k^2) \;</math>; (2) значение решения уменьшается при сжатии ребер графа и, возможно, при удалении ребер. Многие задачи являются двумерными; можно привести такие классические примеры, как [[вершинное покрытие]], [[доминирующее множество]] и [[разрывающее множество]] вершин. | ||
== Классы графов == | == Классы графов == | ||
| Строка 7: | Строка 6: | ||
Первые два класса задач относятся к вложениям в плоскость. Граф является планарным, если он может быть изображен на плоскости или сфере без пересечения дуг. Граф имеет (эйлеров) род не более g, если он может быть изображен на плоскости с эйлеровой характеристикой g. Класс графов имеет ограниченный род, если каждый граф класса имеет род не более g при фиксированном g. | Первые два класса задач относятся к вложениям в плоскость. Граф является [[планарный граф|планарным]], если он может быть изображен на плоскости или сфере без пересечения дуг. Граф имеет (эйлеров) [[род графа|род]] не более g, если он может быть изображен на плоскости с эйлеровой характеристикой g. Класс графов имеет ''ограниченный род'', если каждый граф класса имеет род не более g при фиксированном g. | ||
Следующие три класса задач касаются исключения миноров. Пусть дано ребро e = {v, w} в графе G. Сжатие ребра e в графе G заключается в определении вершин v и w в G и удалении всех циклов и дублирующихся ребер. Граф H, полученный в результате последовательности таких операций сжатия ребер в исходном графе G, называется сжатием графа G. Граф H называется минором графа G, если H является подграфом некоторого сжатия G. Класс графов C является замкнутым относительно операции взятия минора, если любой минор любого графа из C также является членом C. Класс графов C, замкнутый относительно операции взятия минора, | Следующие три класса задач касаются исключения миноров. Пусть дано ребро e = {v, w} в графе G. [[Сжатие ребра]] e в графе G заключается в определении вершин v и w в G и удалении всех циклов и дублирующихся ребер. Граф H, полученный в результате последовательности таких операций сжатия ребер в исходном графе G, называется ''сжатием'' графа G. Граф H называется [[минор графа|минором]] графа G, если H является подграфом некоторого сжатия G. Класс графов C является ''замкнутым относительно операции взятия минора'', если любой минор любого графа из C также является членом C. Класс графов C, замкнутый относительно операции взятия минора, является ''свободным от H-миноров'', если <math>H \notin C \;</math>. В более общем смысле, термин «свободный от H-миноров» относится к любому классу графов, замкнутому относительно операции взятия минора, который не включает некоторый фиксированный граф H. ''Граф с однократным пересечением'' представляет собой минор графа, который может быть изображен на плоскости так, что в нем будет пересекаться не более одной пары ребер. Класс графов, замкнутый относительно операции взятия минора, является ''свободным от миноров с однократным пересечением'', если из него исключен фиксированный граф с однократным пересечением. [[Apex graph|Апексным графом]] называется граф, который становится планарным при удалении из него некоторой вершины. Класс графов является ''свободным от апексных миноров'', если из него исключен некоторый фиксированный апексный граф. | ||
== Двумерные параметры == | == Двумерные параметры == | ||
Неявно понятие «двумерный» подразумевалось в различных работах [2, 5, 10, 11], однако первое явное упоминание было сделано в работе [3]. | Неявно понятие «двумерный» подразумевалось в различных работах [2, 5, 10, 11], однако первое явное упоминание было сделано в работе [3]. | ||
Во-первых, подход с использованием параметров – это альтернативный взгляд на задачи оптимизации. [[Параметр]] P представляет собой функцию, отображающую графы на неотрицательные целые числа. [[Задача разрешимости]], связанная с P, для заданного графа G и неотрицательного целого числа k спрашивает, выполняется ли соотношение <math>P(G) \le k \;</math>. Многие задачи оптимизации могут быть сформулированы в виде подобных задач разрешимости для графового параметра P. | |||
Параметр является ''g(r)-двумерным'' (или просто ''двумерным''), если он равен не менее чем g(r) в «графе-решетке» размером <math>r \times r \;</math> и если он не повышается при взятии миноров (''g(r)-минорно-двумерный'') либо выполнении сжатий (''g(r)-сжато-двумерный''). Точное определение «графа-решетки» зависит от класса допустимых графов и от того, рассматривается ли минорная двумерность или двумерность со сжатием. Для случая минорной двумерности и для любого класса графов, свободного от H-миноров, «графом-решеткой» является [[решетка]] <math>r \times r \;</math>, т.е. планарный граф с <math>r^2 \;</math> вершин, расположенных в виде квадратной решетки, ребра которой связывают горизонтально и вертикально смежные вершины. В случае двумерности со сжатием «граф-решетка» определяется следующим образом: | |||
1. Для планарных графов и графов, свободных от миноров, с однократным пересечением, «граф-решетка» представляет собой решетку <math>r \times r \;</math>, частично [[триангуляция графа|триангулированную]] дополнительными ребрами, сохраняющими планарность. | |||
2. Для графов с ограниченным родом «граф-решетка» представляет собой такую частично триангулированную решетку <math>r \times r \;</math> с дополнительными ребрами («ручками») числом не более genus(G). | |||
3. Для графов, свободных от апексных миноров, «граф-решетка» представляет собой решетку <math>r \times r \;</math> с дополнительными ребрами, такую, что каждая вершина инцидентна O(1) ребер, ведущих к неграничным вершинам решетки. (Здесь O(1) зависит от исключенного апексного графа). | |||
Таким образом, двумерность со сжатием не определена для графов, свободных от H-миноров (или графов общего вида). | |||
Примерами двумерных параметров могут служить количество вершин, диаметр и размеры различных структур – таких как [[разрывающее множество вершин]], [[вершинное покрытие]], минимальное [[паросочетание]] с максимальным весом, [[покрытие гранями]], серия параметров для удаления вершин, [[доминирующее множество]], доминирующее множество ребер, R-доминирующее множество, [[связное доминирующее множество]], связное доминирующее множество ребер, связное R-доминирующее множество, невзвешенная [[метрическая задача коммивояжера]] (обход графа с посещением всех вершин) и [[хордальное дополнение]] (заполнение). Например, разрывающее множество вершин является <math>\Omega (r^2) \;</math>-минорно-двумерным (и, следовательно, сжато-двумерным), поскольку: (1) удаление или сжатие ребра сохраняет существующие разрывающие множества вершин; (2) любая вершина разрывающего множества вершин разрушает не более четырех квадратов решетки <math>r \times r \;</math>, а поскольку всего имеется <math>(r - 1)^2 \;</math> квадратов, любое разрывающее множество вершин должно содержать <math>\Omega (r^2) \;</math> вершин. В [1, 3] можно ознакомиться с рассуждениями по поводу минорной двумерности и двумерности со сжатием для других параметров. | |||
== Основные результаты == | |||
Задача о двумерности строится на базе основополагающей теории о минорах графа Робертсона и Сеймура при помощи расширения некоторых математических результатов и построения новых алгоритмических инструментов. Несколько важных результатов в задачах о двумерности были получены на основе следующих комбинаторных утверждений. Первое из них связывает любой параметр двумерности с древесной шириной, второе – древесную ширину с минорами решетки. | |||
'''Теорема 1 ([1, 8]). Если параметр P является g(r)-двумерным, то для любого графа G из семейства, ассоциированного с параметром P, <math>tw(G) = O(g^{-1} P(G))) \;</math>. В частности, если <math>g(r) = \Theta (r^2) \;</math>, то граница превращается в <math>tw(G) = O( \sqrt{P(G)}) \;</math>.''' | |||
'''Теорема 2 ([8]). Для любого фиксированного графа H любой свободный от H-миноров граф с древесной шириной w имеет в качестве минора решетку <math>\Omega(w) \times \Omega(w) \;</math>.''' | |||
Двумя главными алгоритмическими подходами к задаче двумерности являются субэкспоненциальный алгоритм общего вида с фиксированными параметрами и общая [[аппроксимационная схема с полиномиальным временем выполнения]] (PTAS): | |||
'''Теорема 3 ([1, 8]). Рассмотрим g(r)-двумерный параметр P, который может быть вычислен на графе G за время <math>h(w)n^{O(1)} \;</math> при наличии древесной декомпозиции графа G шириной не более w. Существует алгоритм, вычисляющий P на любом графе G из соответствующего P класса графов с временем выполнения <math>[h(O(g^{-1} (k))) + 2^{O(g^{-1}(k))}] n^{O(1)} \;</math>. В частности, если <math>g(r) = \Theta (r^2) \;</math> и <math>h(w) = 2^{o(w^2)} \;</math>, то это время выполнения является субэкспоненциальным относительно k.''' | |||
'''Теорема 4 ([7]). Рассмотрим задачу двумерности, удовлетворяющую «свойству отделимости», определенному в [4, 7]. Предположим, что эта задача может быть решена на графе G с n вершинами за время f(n, tw(G)). Предположим также, что задача может быть аппроксимирована с коэффициентом <math>\alpha \;</math> за время g(n). Далее, для задачи двумерности со сжатием предположим далее, что оба этих алгоритма также применяются к «обобщенной форме» задачи, определенной в [4, 7]. Тогда существует алгоритм <math>(1 + \epsilon) \;</math>-аппроксимации задачи двумерности, время выполнения которого составляет <math>O(n f (n, O( \alpha^2 / \epsilon)) + n^3 g(n)) \;</math> для соответствующего класса графов.''' | |||
== Применение == | |||
Вышеприведенные теоремы широко применяются в комбинаторных и алгоритмических контекстах. | |||
Применяя границу параметра и древесной ширины из теоремы 1 к параметру в виде количества вершин графа, можно доказать, что каждый граф, свободный от H-миноров, с n вершинами имеет древесную ширину <math>O( \sqrt{n})</math>, что служит (повторным) доказательством теоремы о сепараторах для графов, свободных от H-миноров. Применяя границу параметра и древесной ширины из теоремы 1 к параметру в виде диаметра графа, можно доказать более сильную форму отношения Эппштейна между диаметром и древесной шириной для графов, свободных от апексных миноров. (Далее можно показать, как еще больше усилить соотношение диаметра и древесной ширины до линейного [6]). Соотношение древесной ширины и решетки из теоремы 2 может использоваться для определения границы разрыва между полуцелым и дробным алгоритмами управления несколькими товарными потоками в свободных от H-миноров графах. Оно также дает O(1)-аппроксимацию древесной ширины для графов, свободных от H-миноров. Субэкспоненциальные алгоритмы с фиксированными параметрами из теоремы 3 подтверждают либо усиливают все подобные предыдущие результаты. Эти результаты также можно обобщить для получения алгоритмов с фиксированными параметрами на произвольных графах. В частности, аппроксимационные схемы с полиномиальным временем выполнения (PTAS) из теоремы 4 позволяют получить первые PTAS для связного доминирующего множества и разрывающего множества вершин даже для планарных графов. Более детальное описание всех этих результатов можно найти в [4]. | |||
== Открытые вопросы == | |||
В теории двумерности и родственных направлениях остаются нерешенными несколько комбинаторных и алгоритмических задач. | |||
Можно ли обобщить теорему 2 о соотношении древесной ширины и решетки в свободных от H-миноров графах на произвольные графы с полиномиальным соотношением между древесной шириной и наибольшим минором-решеткой? (Наилучшее известное соотношение является экспоненциальным). Подобные полиномиальные обобщенные подходы были получены для случаев «графов-карт» и «графов высоких степеней» [9]. Удачные границы соотношения древесной ширины и решетки находят применение в минорно-двумерных задачах. | |||
Можно ли обобщить алгоритмические результаты (теоремы 3 и 4) для решения задач о двумерности со сжатием, не ограничивающихся графами, свободными от апексных миноров? Известно, что лежащая в основе этих результатов теорема 1 не допускает обобщения [1]. Тем не менее, теорему 3 удалось обобщить для одной конкретной задачи о двумерности со сжатием – доминирующего множества [3]. | |||
Можно ли обобщить аппроксимационные схемы с полиномиальным временем выполнения из теоремы 4 до алгоритмических задач более общего вида, не сопоставленных напрямую с двумерными параметрами? Один пример семейства подобных задач общего вида появляется при назначении вершинам и/или ребрам весов и необходимости вычислить, например, доминирующее множество с минимальным весом. Еще один пример такой задачи возникает при накладывании ограничений (например, на покрытие или доминирование) только на подмножества вершин и/или ребер. В качестве примеров таких задач можно привести алгоритмы построения дерева Штейнера и разрывающего множества вершин. | |||
Другие открытые вопросы и подробное изложение перечисленных можно найти в [4]. | |||
== См. также == | |||
* ''[[Аппроксимационные схемы для задач с планарными графами]] | |||
* ''[[Путевая ширина графа]] | |||
* ''[[Древесная ширина графа]] | |||
== Литература == | |||
1. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discret. Math. 18(3), 501-511 (2004) | |||
2. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33-47 (2005) | |||
3. Demaine, E.D., Fomin, F.V., Hajiaghayi, M.,Thilikos, D.M.: Subexponential parametrized algorithms on graphs of bounded genus and H-minor-free graphs. J. ACM 52(6), 866-893 (2005) | |||
4. Demaine, E.D., Hajiaghayi, M.:The bidimensionality theory and its algorithmic applications. Comput. J. 51(3) (2008) | |||
5. Demaine, E.D., Hajiaghayi, M.: Diameter and treewidth in minor-closed graph families, revisited. Algorithmica 40(3),211-215(2004) | |||
6. Demaine, E.D., Hajiaghayi, M.: Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA'04), January 2004, pp. 833-842 (2004) | |||
7. Demaine, E.D., Hajiaghayi, M.: Bidimensionality: New connections between FPT algorithms and PTASs. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 590-601. Vancouver, January (2005) | |||
8. Demaine, E.D., Hajiaghayi, M.: Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 682-689. Vancouver, January (2005) | |||
9. Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.: Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction. In: Proceedings of the 17th Annual International Symposium on Algorithms and Computation, Calcutta, India, December 2006. Lecture Notes in Computer Science, vol.4288, pp. 3-15(2006) | |||
10. Demaine, E.D., Hajiaghayi, M., Nishimura, N., Ragde, P., Thilikos, D.M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci. 69(2),166-195(2004) | |||
11. Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica41(4),245-267(2005) | |||
12. Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: The bidimensional theory of bounded-genus graphs. SIAM J. Discret. Math. 20(2), 357-371 (2006) | |||
[[Категория: Совместное определение связанных терминов]] | |||