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

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

Определение

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

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

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

Последовательность сжатия называется -последовательностью, если на протяжении последовательности каждая вершина касается не более чем красных ребер. Двойная ширина графа - это наименьшее значение , для которого он имеет -последовательность. ^[1] ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$

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

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

Говорят, что такое семейство имеет ограниченную разреженную ширину близнеца. ^[3]

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

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

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

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

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

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

В каждом наследственном семействе графов ограниченной двойниковой ширины можно найти семейство полных порядков для вершин его графов, так что унаследованное упорядочение на индуцированном подграфе также является упорядочением в семействе, и так что семейство мало относительно этих порядков. Это означает, что для полного порядка на вершинах число графов в семействе, согласованное с этим порядком, не более чем одинарно экспоненциально по . Наоборот, каждое наследственное семейство упорядоченных графов, которое мало в этом смысле, имеет ограниченную двойниковую ширину. ^[4] Первоначально предполагалось, что каждое наследственное семейство помеченных графов, которое мало в том смысле, что число графов не более чем одинарно экспоненциальный множитель , умноженный на , имеет ограниченную двойниковую ширину. ^[3] Однако эта гипотеза была опровергнута с использованием семейства индуцированных подграфов бесконечного графа Кэли , которые малы как маркированные графы, но не имеют ограниченной ширины близнеца. ^[10] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n!}$

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

• Графы ограниченной степени . ^[1]
• Интервальные графики . ^[1]
• Графы единичного круга . ^[1]

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

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

Если граф имеет ограниченную двойную ширину, то можно найти универсальное дерево сжатий . Это большое семейство последовательностей сжатий, все некоторой (большей) ограниченной ширины, так что на каждом шаге в каждой последовательности есть линейно много непересекающихся пар вершин, каждая из которых может быть сжата на следующем шаге в последовательности. Из этого следует, что количество графов ограниченной двойниковой ширины на любом наборе заданных вершин больше, чем всего лишь на один экспоненциальный множитель, что графы ограниченной двойниковой ширины имеют схему маркировки смежности только с логарифмическим числом бит на вершину, и что они имеют универсальные графы полиномиального размера, в которых каждый -вершинный граф ограниченной двойниковой ширины может быть найден как индуцированный подграф . ^[3] ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle n}$

Алгоритмы

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

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

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

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

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

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

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

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

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

Twin-width также применяется в алгоритмах аппроксимации . В частности, в графах ограниченной twin-width можно найти аппроксимацию к минимальному доминирующему множеству с ограниченным отношением аппроксимации . Это контрастирует с более общими графами, для которых NP-трудно получить отношение аппроксимации, которое лучше логарифмического. ^[6]

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

Ссылки

1. Бонне, Эдуард; Ким, Ын Чжун ; Томассе, Стефан; Ватриган, Реми (2022), «Двойная ширина I: проверка модели управляемого FO», Журнал ACM , 69 (1): A3:1–A3:46, arXiv : 2004.14789 , doi :10.1145/3486655, MR  4402362
2. "Cographs graphs", Информационная система по включению классов графов
3. Бонне, Эдуард; Женье, Колин; Ким, Ын Чжон ; Томассе, Стефан; Ватригант, Реми (2022), «Двойная ширина II: малые классы», Комбинаторная теория , 2 (2): P10:1–P10:42, arXiv : 2006.09877 , doi :10.5070/C62257876, MR  4449818
4. Bonnet, Édouard; Giocanti, Ugo; de Mendez, Patrice Ossona; Simon, Pierre; Thomassé, Stéphan; Torunczyk, Szymon (2022), "Twin-width IV: ordered graphs and matrices", в Leonardi, Stefano; Gupta, Anupam (ред.), STOC '22: 54-й ежегодный симпозиум ACM SIGACT по теории вычислений, Рим, Италия, 20–24 июня 2022 г. , Association for Computing Machinery, стр. 924–937, arXiv : 2102.03117 , doi : 10.1145/3519935.3520037, ISBN 978-1-4503-9264-8, S2CID  235743245
5. Бонне, Эдуард; Ким, Ын Чжун ; Рейнальд, Амадей; Томассе, Стефан (2022), «Двойная ширина VI: линза последовательностей сжатия», в Наор, Джозеф (Сеффи); Бухбиндер, Нив (ред.), Труды симпозиума ACM-SIAM 2022 года по дискретным алгоритмам, SODA 2022, Виртуальная конференция / Александрия, Вирджиния, США, 9–12 января 2022 г. , Общество промышленной и прикладной математики, стр. 1036–1056, arXiv : 2111.00282 , doi : 10.1137/1.9781611977073.45, ISBN 978-1-61197-707-3, S2CID  240354166
6. Бонне, Эдуард; Жене, Колин; Ким, Ын Чжун ; Томассе, Стефан; Ватриган, Реми (2021), «Двойная ширина III: максимальное независимое множество, минимальное доминирующее множество и раскраска», в Бансал, Нихил; Мерелли, Эмануэла; Уоррелл, Джеймс (ред.), 48-й Международный коллоквиум по автоматам, языкам и программированию, ICALP 2021, 12–16 июля 2021 г., Глазго, Шотландия (виртуальная конференция) , LIPIcs, т. 198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 35:1–35:20, arXiv : 2007.14161 , doi : 10.4230/LIPIcs.ICALP.2021.35 , ISBN 9783959771955, S2CID  235736798
7. Дуймович, Вида ; Эппштейн, Дэвид ; Хикингботам, Роберт; Морин, Пэт ; Вуд, Дэвид Р. (август 2021 г.), «Число стека не ограничено числом очереди», Combinatorica , 42 (2): 151–164, arXiv : 2011.04195 , doi : 10.1007/s00493-021-4585-7, S2CID  226281691
8. Бонне, Эдуард; Ким, Ын Чжон ; Рейнальд, Амадей; Томассе, Стефан; Ватригант, Реми (2022), «Двойные и полиномиальные ядра», Algorithmica , 84 (11): 3300–3337, arXiv : 2107.02882 , doi : 10.1007/s00453-022-00965-5, MR  4500778
9. Петтерссон, Уильям; Петтерссон, Джон (июнь 2023 г.), «Границы двойной ширины графов произведений», Дискретная математика и теоретическая информатика , 25 (1), arXiv : 2202.11556 , doi : 10.46298/dmtcs.10091
10. Бонне, Эдуард; Женье, Колин; Тессера, Ромен; Томассе, Стефан (2022), «Двойная ширина VII: группы», arXiv : 2204.12330 [math.GR]
11. Берже, Пьер; Бонне, Эдуард; Депре, Хьюг (2022), «Определение ширины близнеца не более 4 является NP-полным», в Боянчике, Миколае; Мерелли, Эмануэла; Вудрафф, Дэвид П. (ред.), 49-й Международный коллоквиум по автоматам, языкам и программированию, ICALP 2022, 4–8 июля 2022 г., Париж, Франция , LIPics, vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 18:1–18:20, arXiv : 2112.08953 , doi : 10.4230/LIPIcs.ICALP.2022.18 , ISBN 9783959772358, S2CID  245218775
12. Шидлер, Андре; Сейдер, Стефан (2022), «Подход SAT к ширине близнеца», в Филлипс, Синтия А .; Спекманн, Беттина (ред.), Труды симпозиума по разработке алгоритмов и экспериментам, ALENEX 2022, Александрия, Вирджиния, США, 9–10 января 2022 г. , Общество промышленной и прикладной математики, стр. 67–77, arXiv : 2110.06146 , doi : 10.1137/1.9781611977042.6, ISBN 978-1-61197-704-2, S2CID  238634418
13. Саймон, Пьер; Торунчик, Шимон (2021), Упорядоченные графы ограниченной двойной ширины , arXiv : 2102.06881
14. Пилипчук, Марек; Соколовский, Михал (2023), «Графы ограниченной двойниковой ширины квазиполиномиально ограничены», Журнал комбинаторной теории, Серия B , 161 : 382–406, arXiv : 2202.07608 , doi : 10.1016/j.jctb.2023.02.006, MR  4568111, S2CID  247170805 ${\displaystyle \chi }$
15. Дрейер, Ян; Гаярский, Якуб; Цзян, Итин; Оссона де Мендес, Патрис; Рэймонд, Жан-Флоран (2022), «Двойная ширина и обобщенные числа раскраски», Дискретная математика , 345 (3), Статья 112746, arXiv : 2104.09360 , doi : 10.1016/j.disc.2021.112746, MR  4349879, S2CID  233296212
16. Берже, Пьер; Бонне, Эдуард; Депре, Хьюг; Ватригант, Реми (2023), «Аппроксимация крайне неаппроксимируемых задач на графах ограниченной ширины двойника», в Беренбринк, Петра; Буйе, Патрисия ; Давар, Анудж; Канте, Мамаду Мустафа (ред.), 40-й Международный симпозиум по теоретическим аспектам информатики, STACS 2023, 7–9 марта 2023 г., Гамбург, Германия , LIPIcs, vol. 254, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 10:1–10:15, arXiv : 2207.07708 , doi : 10.4230/LIPIcs.STACS.2023.10

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

• Ahn, Jungho; Hendrey, Kevin; Kim, Donggyu; Oum, Sang-Il (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 -смешанно-тонких графов», в Bekos, Michael A.; Кауфманн, Майкл (ред.), Графовые теоретические концепции в информатике - 48-й международный семинар, WG 2022, Тюбинген, Германия, 22–24 июня 2022 г., Пересмотренные избранные статьи , Lecture Notes in Computer Science, т. 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 – Leibniz-Zentrum für Informatik, стр. 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) , Издательство Масарикова университета, стр. 156–162, arXiv : 2102.06880 , doi : 10.5817/cz.muni.eurocomb23-022
• Гаярский, Якуб; Пилипчук, Михал; Пшибышевский, Войцех; Торуньчик, Шимон (2022), «Двойная ширина и типы», Боянчик, Миколай; Мерелли, Эмануэла; Вудрафф, Дэвид П. (ред.), 49-й Международный коллоквиум по автоматам, языкам и программированию, ICALP 2022, 4–8 июля 2022 г., Париж, Франция , LIPics, vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 123:1–123:21, arXiv : 2206.08248 , doi : 10.4230/LIPIcs.ICALP.2022.123 , ISBN 9783959772358
• Gajarský, Jakub; Pilipczuk, Michal; Toruńczyk, Szymon (2022), «Стабильные графы ограниченной двойной ширины», в Baier, Christel ; Fisman, Dana (ред.), LICS '22: 37-й ежегодный симпозиум ACM/IEEE по логике в компьютерных науках, Хайфа, Израиль, 2–5 августа 2022 г. , Association for Computing Machinery, стр. 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, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 53:1–53:14, arXiv : 2207.07683 , doi : 10.4230/LIPICS.ESA.2023.53 , S2CID  261345465
• Jacob, Hugo; Pilipczuk, Marcin (2022), «Ограничение ширины близнеца для графов с ограниченной древовидной шириной, планарных графов и двудольных графов», в Bekos, Michael A.; Kaufmann, Michael (ред.), Графовые теоретические концепции в информатике – 48-й международный семинар, WG 2022, Тюбинген, Германия, 22–24 июня 2022 г., Revised Selected Papers , Lecture Notes in Computer Science, т. 13453, Springer, стр. 287–299, arXiv : 2201.09749 , doi : 10.1007/978-3-031-15914-5_21, ISBN 978-3-031-15913-8
• Pilipczuk, Michal; Sokolowski, Marek; Zych-Pawlewicz, Anna (2022), «Компактное представление для матриц ограниченной двойной ширины», в Berenbrink, Petra; Monmege, Benjamin (ред.), 39-й Международный симпозиум по теоретическим аспектам компьютерной науки, STACS 2022, 15–18 марта 2022 г., Марсель, Франция (виртуальная конференция) , LIPIcs, т. 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
• Przybyszewski, Wojciech (2022), VC-плотность и абстрактная ячеечная декомпозиция для отношения ребер в графах ограниченной двойниковой ширины , arXiv : 2202.04006
• Томассе, Стефан (2022), «Краткий тур в двойной ширине (приглашенный доклад)», в Боянчике, Миколай; Мерелли, Эмануэла; Вудрафф, Дэвид П. (ред.), 49-й Международный коллоквиум по автоматам, языкам и программированию, ICALP 2022, 4–8 июля 2022 г., Париж, Франция , LIPics, vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 6:1–6:5, doi : 10.4230/LIPIcs.ICALP.2022.6 , ISBN 9783959772358