Двойная ширина

Двойная ширина неориентированного графа — это натуральное число, связанное с графом, используемое для изучения параметризованной сложности графовых алгоритмов . Интуитивно он измеряет, насколько граф похож на кограф — тип графа, который можно свести к одной вершине путем многократного слияния двойников , — вершин имеющих одинаковых соседей . Ширина двойника определяется последовательностью повторяющихся слияний, где вершины не обязательно должны быть двойниками, но имеют почти равные наборы соседей.

Определение

Двойная ширина определяется для конечных простых неориентированных графов. Они имеют конечный набор вершин и набор ребер , которые представляют собой неупорядоченные пары вершин. Открытая окрестность любой вершины — это множество других вершин, с которыми она соединена в ребрах графа; закрытая окрестность формируется из открытой окрестности путем включения самой вершины. Две вершины являются истинными близнецами, если они имеют одинаковую замкнутую окрестность, и ложными близнецами, если они имеют одинаковую открытую окрестность; В более общем смысле, как истинных, так и ложных близнецов можно называть близнецами без оговорок.

Кографы имеют множество эквивалентных определений, но один из них заключается в том, что это графы, которые можно свести к одной вершине путем многократного поиска любых двух вершин-близнецов и объединения их в одну вершину. Для кографа этот процесс редукции всегда будет успешным, независимо от того, какой выбор близнецов для слияния делается на каждом этапе. Граф, не являющийся кографом, всегда застревает в подграфе с более чем двумя вершинами, не имеющем двойников.

Определение ширины двойника имитирует этот процесс сокращения. Последовательность сокращения в данном контексте — это последовательность шагов, начинающаяся с заданного графа, в которой каждый шаг заменяет пару вершин одной вершиной. В результате получается последовательность графов с ребрами, окрашенными в красный и черный цвета; в данном графе все ребра считаются черными. Когда две вершины заменяются одной вершиной, окрестность новой вершины представляет собой объединение окрестностей замененных вершин. В этой новой окрестности ребро, исходящее из черных ребер в окрестностях обеих вершин, остается черным; все остальные края окрашены в красный цвет.

Последовательность сокращений называется $d$-последовательность, если на протяжении всей последовательности каждая вершина соприкасается не более чем $d$ красные края. Двойная ширина графа — это наименьшее значение $d$ для чего у него есть $d$-последовательность.

все Плотный граф еще может иметь ограниченную ширину двойника; например, кографы включают все полные графы . Вариант двойной ширины, разреженная двойная ширина , применяется к семействам графов, а не к отдельным графам. Для семейства графов, замкнутого относительно взятия индуцированных подграфов и имеющего ограниченную двойниковую ширину, следующие свойства эквивалентны:

• Графы в этом семействе разрежены, что означает, что они имеют количество ребер, ограниченное линейной функцией от количества вершин.
• Графы в семействе исключают некоторый фиксированный полный двудольный граф в качестве подграфа.
• Семейство всех подграфов графов данного семейства имеет ограниченную двойниковую ширину.
• Семья имеет ограниченное расширение , а это означает, что все ее мелкие второстепенные элементы редки.

Говорят, что такое семейство имеет ограниченную разреженную двойную ширину.

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

Графы ограниченной двойниковой ширины

Кографы имеют нулевую двойную ширину. В процессе редукции кографов не будет красных ребер: когда две вершины объединяются, их окрестности равны, поэтому нет ребер, исходящих только из одной из двух окрестностей, которые можно было бы покрасить в красный цвет. В любом другом графе любая сжимающая последовательность создаст несколько красных ребер, а ширина двойника будет больше нуля.

Графы путей , имеющие не более трех вершин, являются кографами, но каждый граф путей большего размера имеет двойную ширину. Для сжимающей последовательности, которая неоднократно объединяет два последних ребра пути, только ребро, инцидентное единственной объединенной вершине, будет красным, так что это 1-последовательность. Деревья имеют не более двух двойных ширин, а для некоторых деревьев это очень мало. Последовательность 2-сокращений для любого дерева можно найти, выбрав корень, а затем повторно объединив два листа, имеющих одного и того же родителя, или, если это невозможно, объединив самый глубокий лист с его родителем. Единственные красные края соединяют листья с их родителями, и когда их два у одного родителя, их можно объединить, сохранив степень красного цвета не более двух.

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

• Каждый граф ограниченной ширины клики или ограниченной ширины ранга также имеет ограниченную ширину близнеца. Двойная ширина не более чем экспоненциальна по ширине клики и не более чем в два раза экспоненциальна по ширине ранга. К таким графам относятся, например, дистанционно-наследственные графы , степени k -листьев для ограниченных значений k и графы ограниченной ширины дерева .
• Графы безразличия (эквивалентно графам единичных интервалов или графам собственных интервалов) имеют ширину близнеца не более двух.
• Графы единичных дисков, определенные из наборов единичных дисков, которые покрывают каждую точку плоскости ограниченное количество раз, имеют ограниченную ширину двойника. То же самое верно и для графов единичных шаров в более высоких измерениях.
• Графы перестановок , возникающие в результате перестановок с запрещенным шаблоном перестановок, имеют ограниченную ширину двойника. Это позволяет применять двойную ширину к алгоритмическим задачам, связанным с перестановками с запрещенными шаблонами.
• Каждое семейство графов, определяемое запрещенными минорами, имеет ограниченную двойниковую ширину. Например, по теореме Вагнера запрещенными минорами для плоских графов являются два графа $K_{5}$ и $K_{3,3}$, поэтому плоские графы имеют ограниченную двойниковую ширину.
• Каждый граф ограниченного числа стека или ограниченного числа очередей также имеет ограниченную ширину двойника. Существуют семейства графов ограниченной разреженной двойниковой ширины, не имеющие ограниченного числа стека, но соответствующий вопрос о номере очереди остается открытым.
• Сильное произведение любых двух графов ограниченной ширины близнеца, один из которых имеет ограниченную степень, снова имеет ограниченную ширину близнеца. Это можно использовать для доказательства ограниченной двойниковой ширины классов графов, которые разлагаются на сильные произведения путей и графов с ограниченной древовидной шириной, таких как k -планарные графы . Для лексикографического продукта графов двойниковая ширина равна точно максимальной из ширин двух факторных графов. Двойная ширина также хорошо работает с некоторыми другими стандартными графовыми продуктами, но не с модульным продуктом графов .

В каждом наследственном семействе графов ограниченной двойниковой ширины можно найти такое семейство полных порядков вершин его графов, что наследуемый порядок в индуцированном подграфе также является порядком в семействе и что семейство мал по отношению к этим порядкам. Это означает, что для общего заказа на $n$ вершин, число графов в семействе, соответствующих этому порядку, не более чем одноэкспоненциально $n$. И наоборот, каждое малое в этом смысле наследственное семейство упорядоченных графов имеет ограниченную ширину двойника. Первоначально предполагалось, что каждое наследственное семейство помеченных графов является небольшим в том смысле, что количество графов не превышает одного экспоненциального множителя, умноженного на один экспоненциальный множитель. $n!$, имеет ограниченную двойную ширину. Однако эта гипотеза была опровергнута с использованием семейства индуцированных подграфов бесконечного графа Кэли , которые малы как помеченные графы, но не имеют ограниченной двойниковой ширины.

Существуют графы неограниченной двойниковой ширины внутри следующих семейств графов:

• Графы ограниченной степени .
• Интервальные графики .
• Дисковые графы единиц .

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

Характеристики

Если граф имеет ограниченную двойниковую ширину, то можно найти универсальное дерево сокращений . Это большое семейство сжимающих последовательностей, все из которых имеют некоторую (большую) ограниченную ширину, так что на каждом шаге в каждой последовательности существует линейно много непересекающихся пар вершин, каждая из которых может быть свернута на следующем шаге последовательности. Отсюда следует, что число графов ограниченной двойниковой ширины на любом множестве $n$ заданных вершин больше, чем $n!$ только на один экспоненциальный коэффициент, что графы с ограниченной шириной близнеца имеют схему разметки смежности только с логарифмическим числом битов на вершину и что они имеют универсальные графы полиномиального размера, в которых каждый $n$Граф вершин ограниченной ширины двойника можно найти как индуцированный подграф .

Алгоритмы

Графики ширины двойника не более одного можно распознать за полиномиальное время . Однако NP-полно определить, имеет ли данный граф ширину двойника не более четырех, и NP-трудно аппроксимировать ширину двойника с коэффициентом аппроксимации лучше 5/4. Согласно гипотезе экспоненциального времени , вычисление ширины двойника требует времени, по крайней мере, экспоненциального в $n/\log n$, на $n$-вершинные графы. На практике можно вычислить двойниковую ширину графов среднего размера с помощью решателей SAT . Для большинства известных семейств графов ограниченной ширины-близнеца можно построить сжимающую последовательность ограниченной ширины за полиномиальное время.

После того, как сжимающая последовательность задана или построена, с ее помощью можно решить множество различных алгоритмических задач, во многих случаях более эффективно, чем это возможно для графов, которые не имеют ограниченной ширины двойника. Как подробно описано ниже, к ним относятся точные параметризованные алгоритмы и алгоритмы аппроксимации для NP-сложных задач, а также некоторые задачи, которые имеют классические алгоритмы с полиномиальным временем, но, тем не менее, могут быть ускорены с использованием предположения об ограниченной двойниковой ширине.

Параметризованные алгоритмы

Алгоритмическая задача на графах, имеющих связанный параметр, называется разрешимой с фиксированным параметром, если она имеет алгоритм, который на графах с $n$ вершины и значение параметра $k$, бежит во времени $O(n^{c}\,f(k))$ для некоторой константы $c$ и вычислимая функция $f$. Например, время работы $O(n2^{k})$ в этом смысле будет управляемым с фиксированными параметрами. Этот стиль анализа обычно применяется к задачам, для которых нет известного алгоритма с полиномиальным временем , поскольку в противном случае управляемость с фиксированными параметрами была бы тривиальной. Было показано, что многие такие проблемы решаются с фиксированными параметрами, используя ширину двойника в качестве параметра, когда в качестве входных данных задается последовательность сжатия ограниченной ширины. Это относится, в частности, к перечисленным выше семействам графов ограниченной ширины двойника, для которых можно эффективно построить сжимающую последовательность. Однако неизвестно, как найти хорошую сжимающую последовательность для произвольного графа с малой шириной двойника, если никакая другая структура в графе не известна.

Решаемые проблемы с фиксированным параметром для графов ограниченной ширины двойника с заданными сжимающими последовательностями включают:

• Проверка того, моделирует ли данный граф какое-либо заданное свойство в логике графов первого порядка . Здесь и ширина двойника, и длина описания свойства являются параметрами анализа. Проблемы этого типа включают изоморфизм подграфов для подграфов ограниченного размера, а также проблемы вершинного покрытия и доминирующего множества для покрытий или доминирующих множеств ограниченного размера. Зависимость этих общих методов от длины логической формулы, описывающей свойство, является тетрационной , но для независимого множества, доминирующего множества и связанных с ними задач может быть сведена к экспоненциальной по размеру независимого или доминирующего множества, а для изоморфизма подграфов его можно свести к факториалу числа вершин подграфа. Например, время найти $k$-вершинно-независимый набор для $n$-вершинный граф с заданным $d$-последовательность, это $O(k^{2}d^{2k}n)$, с помощью алгоритма динамического программирования , который рассматривает небольшие связные подграфы красных графов в прямом направлении сокращающейся последовательности. Эти временные границы оптимальны с точностью до логарифмических коэффициентов экспоненты в соответствии с гипотезой экспоненциального времени . Для расширения логики графов первого порядка на графы с полностью упорядоченными вершинами и логическими предикатами, которые могут проверить этот порядок, проверка модели по-прежнему доступна с фиксированными параметрами для наследственных семейств графов с ограниченной шириной двойника, но не (в соответствии со стандартом предположения теории сложности) для наследственных семейств неограниченной ширины близнеца.
• Раскраска графов ограниченной ширины двойника с использованием количества цветов, ограниченного функцией ширины двойника и размера наибольшей клики . Например, без треугольников графы двойниковой ширины $d$ может быть $(d+2)$-раскрашивается с помощью жадного алгоритма окраски , который окрашивает вершины в обратном порядке, в котором они были свернуты. Этот результат показывает, что графы ограниченной ширины двойника χ-ограничены . Для семейств графов ограниченной разреженной ширины близнеца числа обобщенной раскраски ограничены. Здесь обобщенное число раскраски $\operatorname {col} _{r}(G)$ самое большее $k$ если вершины можно линейно упорядочить так, что каждая вершина может достигать не более $k-1$ более ранние вершины в порядке, через пути длины $r$ через более поздние вершины в порядке.

Ускорения классических алгоритмов

В графах ограниченной ширины двойника можно выполнить поиск в ширину на графе с $n$ вершины во времени $O(n\log n)$, даже если граф плотный и имеет больше ребер, чем это ограничение по времени.

Алгоритмы аппроксимации

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

Задачи о максимальном независимом множестве и раскраске графов могут быть аппроксимированы с точностью до коэффициента аппроксимации $n^{\varepsilon }$, для каждого $\varepsilon >0$, за полиномиальное время на графах ограниченной ширины двойника. Напротив, без предположения об ограниченной ширине двойника NP-трудно достичь какого-либо коэффициента аппроксимации этой формы с $\varepsilon <1$.

Дальнейшее чтение

• Ан, Чонхо; Хендри, Кевин; Ким, Донгю; Оум, Санг-Ил (2022), «Границы двойниковой ширины графов», SIAM Journal on Discrete Mathematics , 36 (3): 2352–2366, arXiv : 2110.03957 , doi : 10.1137/21M1452834 , MR   4487903
• Балабан, Якуб; Хлинены, Петр (2021), «Двойная ширина линейна по ширине частичного множества», в Головаче, Петр А.; Зехави, Мейрав (ред.), 16-й Международный симпозиум по параметризованным и точным вычислениям, IPEC 2021, 8–10 сентября 2021 г., Лиссабон, Португалия , LIPIcs, vol. 214, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 6:1–6:13, arXiv : 2106.15337 , doi : 10.4230/LIPIcs.IPEC.2021.6 , ISBN  9783959772167 , S2CID   235669802
• Балабан, Якуб; Хлиненый, Петр; Едельски, Ян (2022), «Двойная ширина и преобразование правильных k- смешанно-тонких графов», Бекос, Майкл А.; Кауфманн, Михаэль (ред.), Теоретико-графовые концепции в информатике - 48-й международный семинар, WG 2022, Тюбинген, Германия, 22–24 июня 2022 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 13453, Springer, стр. 43–55, arXiv : 2202.12536 , doi : 10.1007/978-3-031-15914-5_4 , ISBN  978-3-031-15913-8
• Бонне, Эдвард; Чакраборти, Дибьяян; Ким, Ын Чжон ; Колер, Нолин; Лопес, Рауль; Томассе, Стефан (2022 г.), «Twin-Width VIII: разграничение и беспроигрышные варианты», Делл, Хольгер; Недерлоф, Йеспер (ред.), 17-й Международный симпозиум по параметризованным и точным вычислениям, IPEC 2022, 7–9 сентября 2022 г., Потсдам, Германия , LIPIcs, vol. 249, Schloss Dagstuhl – Центр информатики Лейбница, стр. 9:1–9:18, arXiv : 2204.00722 , doi : 10.4230/LIPIcs.IPEC.2022.9
• Бонне, Эдуард; Депре, Хьюг (2023), «Двойная ширина может быть экспоненциальной по ширине дерева», Журнал комбинаторной теории, серия B , 161 : 1–14, arXiv : 2204.07670 , doi : 10.1016/j.jctb.2023.01.003 , MR   4543125
• Бонне, Эдуард; Джоканти, Уго; де Мендес, Патрис Оссона; Томассе, Стефан (2023), «Двойная ширина V: линейные миноры, модульный подсчет и умножение матриц», в Беренбринк, Петра; Буйе, Патрисия ; Давар, Анудж; Канте, Мамаду Мустафа (ред.), 40-й Международный симпозиум по теоретическим аспектам информатики, STACS 2023, 7–9 марта 2023 г., Гамбург, Германия , LIPIcs, vol. 254, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 15:1–15:16, doi : 10.4230/LIPIcs.STACS.2023.15
• Бонне, Эдуард; Квон, О Чжон; Вуд, Дэвид Р. (2022), «Уменьшенная пропускная способность: качественное усиление двойниковой ширины в второстепенных закрытых классах (и за их пределами)», arXiv : 2202.11858 [ math.CO ]
• Бонне, Эдуард; Нешетржил, Ярослав; Оссона де Мендес, Патрис; Зибертц, Себастьян; Томассе, Стефан (август 2023 г.), «Двойная ширина и перестановки», Европейская конференция по комбинаторике, теории графов и приложениям (EUROCOMB'23) , Masaryk University Press, стр. 156–162, arXiv : 2102.06880 , doi : 10.5817/cz .muni.eurocomb23-022
• Гажарский, Якуб; Пилипчук, Михал; Пшибышевский, Войцех; Торуньчик, Шимон (2022), «Двойная ширина и типы», Боянчик, Миколай; Мерелли, Эмануэла; Вудрафф, Дэвид П. (ред.), 49-й Международный коллоквиум по автоматам, языкам и программированию, ICALP 2022, 4–8 июля 2022 г., Париж, Франция , LIPics, vol. 229, Schloss Dagstuhl - Центр компьютерных наук Лейбница, стр. 123: 1–123: 21, arXiv : 2206.08248 , doi : 10.4230/LIPIcs.ICALP.2022.123 , ISBN  9783959772358
• Гаярский, Якуб; Пилипчук, Михал; Торуньчик, Шимон (2022), «Стабильные графы ограниченной двойниковой ширины», в Байере, Кристель ; Фисман, Дана (ред.), LICS '22: 37-й ежегодный симпозиум ACM/IEEE по логике в информатике, Хайфа, Израиль, 2–5 августа 2022 г. , Ассоциация вычислительной техники, стр. 39:1–39:12, arXiv : 2107.03711 , doi : 10.1145/3531130.3533356 , ISBN  978-1-4503-9351-5
• Великолепно, Колин; Томассе, Стефан (2023), «Логика первого порядка и двойная ширина в турнирах», у Гёрца, Инге Ли; Фарах-Колтон, Мартин ; Пуглиси, Саймон Дж.; Герман, Гжегож (ред.), 31-й ежегодный европейский симпозиум по алгоритмам, ESA 2023, 4–6 сентября 2023 г., Амстердам, Нидерланды , LIPIcs, vol. 274, Замок Дагштуль – Центр компьютерных наук Лейбница, стр. 53:1–53:14, arXiv : 2207.07683 , doi : 10.4230/LIPICS.ESA.2023.53 , S2CID   261345465
• Джейкоб, Хьюго; Пилипчук, Марцин (2022), «Ограничивающая ширина двойника для графов с ограниченной шириной дерева, плоских графов и двудольных графов», в Бекосе, Майкле А.; Кауфманн, Михаэль (ред.), Теоретико-графовые концепции в информатике – 48-й международный семинар, WG 2022, Тюбинген, Германия, 22–24 июня 2022 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 13453, Springer, стр. 287–299, arXiv : 2201.09749 , doi : 10.1007/978-3-031-15914-5_21 , ISBN  978-3-031-15913-8
• Пилипчук, Михал; Соколовский, Марек; Зых-Павлевич, Анна (2022), «Компактное представление матриц ограниченной двойниковой ширины», в Беренбринк, Петра; Монмеж, Бенджамин (ред.), 39-й Международный симпозиум по теоретическим аспектам информатики, STACS 2022, 15–18 марта 2022 г., Марсель, Франция (виртуальная конференция) , LIPics, vol. 219, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 52:1–52:14, arXiv : 2110.08106 , doi : 10.4230/LIPIcs.STACS.2022.52 , ISBN  9783959772228 , S2CID   239009596
• Пшибышевский, Войцех (2022), VC-плотность и разложение абстрактных ячеек для реберного отношения в графах с ограниченной шириной двойника , arXiv : 2202.04006
• Томассе, Стефан (2022), «Краткий тур в двойной ширине (приглашенный доклад)», в Боянчике, Миколай; Мерелли, Эмануэла; Вудрафф, Дэвид П. (ред.), 49-й Международный коллоквиум по автоматам, языкам и программированию, ICALP 2022, 4–8 июля 2022 г., Париж, Франция , LIPics, vol. 229, Schloss Dagstuhl — Центр компьютерных наук Лейбница, стр. 6:1–6:5, doi : 10.4230/LIPIcs.ICALP.2022.6 , ISBN  9783959772358