Токсичность - Boxicity

График пересечений прямоугольников с квадратичностью два

В теория графов, коробочка это инвариант графа, представлен Фред С. Робертс в 1969 г.

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

Примеры

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

Робертс (1969) показал, что график с 2п вершины, образованные удалением идеальное соответствие из полный график на 2п вершины имеют прямоугольность ровно п: каждая пара несвязных вершин должна быть представлена ​​блоками, которые разделены в другом измерении, чем каждая другая пара. Коробочное представление этого графа с размером точно п можно найти, утолщив каждый из 2п грани п-размерный гиперкуб в коробку. Из-за этих результатов этот график был назван Граф Робертса,^[1] хотя он более известен как график коктейльной вечеринки и это также можно понимать как График Турана Т(2п,п).

Отношение к другим классам графов

Граф имеет коробчатость не более единицы тогда и только тогда, когда он интервальный график; коробчатость произвольного графа грамм - минимальное количество интервальных графов на одном и том же множестве вершин, такое что пересечение множеств ребер интервальных графов равно грамм. Каждые внешнепланарный граф имеет размер не более двух,^[2] и каждый планарный граф имеет размер не более трех.^[3]

Если двудольный граф имеет коробчатость два, он может быть представлен как граф пересечений параллельных осям отрезков прямых на плоскости.^[4]

Адига, Боумик и Чандран (2011) доказал, что коробчатость двудольного графа грамм находится в пределах коэффициента 2 от размер заказа высоты-два частично заказанный набор связано с грамм следующим образом: набор минимальных элементов соответствует одному частному набору грамм, множество максимальных элементов соответствует второму частному набору грамм, причем два элемента сравнимы, если соответствующие вершины смежны в грамм. Эквивалентно размер заказа высоты-два частично заказанный набор п находится в 2 раза меньше квадратичного размера график сопоставимости из п (который является двудольным, поскольку п имеет высоту два).

Алгоритмические результаты

Многие задачи с графами могут быть решены или аппроксимированы более эффективно для графов с ограниченной прямоугольностью, чем для других графов; например, проблема максимальной клики может быть решена за полиномиальное время для графов с ограниченной коробчатостью.^[5] Для некоторых других проблем с графами эффективное решение или приближение можно найти, если известно низкоразмерное блочное представление.^[6] Однако найти такое представление может быть сложно: это НП-полный чтобы проверить, не превышает ли квадратность данного графа некоторое заданное значение K, даже для K = 2.^[7]Чандран, Фрэнсис и Сивадасан (2010) описывать алгоритмы поиска представлений произвольных графов в виде графов пересечений ящиков с размерностью, которая находится в пределах логарифмический фактор максимальная степень графа; этот результат дает верхнюю границу коробчатости графа.

Несмотря на то, что он жесткий по своим естественным параметрам, боксичность управляемый с фиксированными параметрами при параметризации крышка вершины номер входного графа.^[8]

Границы

Если график грамм график имеет м края, то:${displaystyle box(G)=O({sqrt {mcdot log(m)}})}$.^[9][10]

Если график грамм является k-выродиться (с участием ${displaystyle kgeq 2}$) и имеет п вершины, то грамм имеет боксерский вид ${displaystyle box(G)leq (k+2)lceil 2elog nceil }$.^[11]

Если график грамм не имеет полного графика на т вершины как незначительный, тогда ${displaystyle box(G)=O(t^{2}log t)}$^[12] а есть графики без полного графика на т вершины как незначительный, и с коробкой ${displaystyle Omega (t{sqrt {log t}})}$.^[13] В частности, любой граф грамм hax boxicity ${displaystyle box(G)=O(mu (G)^{2}log mu (G))}$, куда ${displaystyle mu (G)}$ обозначает Инвариант Колена де Вердьера из грамм.

Связанные инварианты графа

• Кубичность определяется так же, как прямоугольность, но с параллельными осям гиперкубы вместо гипер прямоугольников. Боксичность - это обобщение кубичности.
• Сферичность определяется так же, как коробчатость, но со сферами единичного диаметра.

Примечания

1. Например, см. Чандран, Фрэнсис и Сивадасан (2010) и Чандран и Сивадасан (2007).
2. Шайнерман (1984).
3. Томассен (1986).
4. Bellantoni et al. (1993).
5. Чандран, Фрэнсис и Сивадасан (2010) заметим, что это следует из того факта, что эти графы имеют полиномиальное число максимальные клики. Явное блочное представление не требуется для эффективного перечисления всех максимальных клик.
6. См., Например, Агарвал, ван Кревельд и Сури (1998) и Berman et al. (2001) для приближений к максимальный независимый набор для графиков пересечений прямоугольников и Хлебик и Хлебикова (2005) за результаты о трудности аппроксимации этих задач в более высоких измерениях.
7. Cozzens (1981) показывает, что вычисление квадратичности является NP-полным; Яннакакис (1982) показывает, что даже проверка того, не превышает ли квадратичность 3, является NP-сложной задачей; наконец-то Краточвиль (1994) показал, что распознать коробчатость 2 NP-сложно.
8. Адига, Читнис и Саураб (2010).
9. Чандран, Фрэнсис и Сивадасан (2010)
10. Эсперет (2016)
11. Адига, Чандран и Мэтью (2014)
12. Эсперет и Вихерт (2018)
13. Эсперет (2016)

Рекомендации

• Адига, Абхиджин; Бхоумик, Диптенду; Чандран, Л. Сунил (2011), «Боксичность и размерность позета», Журнал SIAM по дискретной математике, 25 (4): 1687–1698, arXiv:1003.2357, Дои:10.1137/100786290.
• Адига, Абхиджин; Чандран, Л. Сунил; Мэтью, Роджерс (2014), «Кубичность, вырождение и число пересечения», Европейский журнал комбинаторики, 35: 2–12, arXiv:1105.5225, Дои:10.1016 / j.ejc.2013.06.021.
• Адига, Абхиджин; Читнис, Раджеш; Саураб, Сакет (2010), «Параметризованные алгоритмы для боксовости», Алгоритмы и вычисления: 21-й международный симпозиум, ISAAC 2010, остров Чеджу, Корея, 15-17 декабря 2010 г., Материалы, часть I (PDF), Конспект лекций по информатике, 6506, стр. 366–377, Дои:10.1007/978-3-642-17517-6_33, заархивировано из оригинал (PDF) на 2017-08-30, получено 2018-01-22
• Агарвал, Панкадж К.; ван Кревельд, Марк; Сури, Субхаш (1998), «Размещение метки максимально независимым набором в прямоугольниках», Теория вычислительной геометрии и приложения, 11 (3–4): 209–218, Дои:10.1016 / S0925-7721 (98) 00028-5, HDL:1874/18908.
• Bellantoni, Стивен Дж .; Бен-Арройо Хартман, Ирит; Пржитицкая, Тереза; Уайтсайдс, Сью (1993), "Графы пересечений сеток и прямоугольность", Дискретная математика, 114 (1–3): 41–49, Дои:10.1016 / 0012-365X (93) 90354-V.
• Берман, Петр; DasGupta, B .; Muthukrishnan, S .; Рамасвами, С. (2001), "Эффективные алгоритмы аппроксимации для задач замощения и упаковки прямоугольников", J. Алгоритмы, 41 (2): 443–470, Дои:10.1006 / jagm.2001.1188.
• Чандран, Л. Сунил; Фрэнсис, Мэтью С .; Сивадасан, Навин (2010), «Геометрическое представление графиков в низком измерении с использованием параллельных осей прямоугольников», Алгоритмика, 56 (2): 129–140, arXiv:cs.DM/0605013, Дои:10.1007 / s00453-008-9163-5, Г-Н  2576537, S2CID  17838951.
• Чандран, Л. Сунил; Сивадасан, Навин (2007), «Боксичность и ширина дерева», Журнал комбинаторной теории, Серия B, 97 (5): 733–744, arXiv:math.CO/0505544, Дои:10.1016 / j.jctb.2006.12.004, S2CID  9854207.
• Хлебик, Мирослав; Хлебикова, Янка (2005), "Аппроксимационная трудность задач оптимизации в графах пересечений d-габаритные коробки », Материалы шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, стр. 267–276.
• Коззенс, М. Б. (1981), Высшие и многомерные аналоги интервальных графов, Кандидат наук. диссертация, Университет Рутгерса.
• Эспере, Луи (2016), "Боксичность и топологические инварианты", Европейский журнал комбинаторики, 51: 495–499, arXiv:1503.05765, Дои:10.1016 / j.ejc.2015.07.020, S2CID  5548385.
• Эспере, Луи; Вихерт, Файт (2018), "Боксичность, размерность и исключение несовершеннолетних", Электронный журнал комбинаторики, 25 (4): # P4.51, arXiv:1804.00850, Дои:10.37236/7787, S2CID  119148637.
• Краточвил Ян (1994), "Специальная проблема плоской выполнимости и следствие ее NP-полноты", Дискретная прикладная математика, 52 (3): 233–252, Дои:10.1016 / 0166-218X (94) 90143-0.
• Квест, М .; Вегнер, Г. (1990), "Характеристика графов с квадратичностью ≤ 2", Дискретная математика, 81 (2): 187–192, Дои:10.1016 / 0012-365X (90) 90151-7.
• Робертс, Ф.С. (1969), «О коробчатости и кубичности графа», в Тутте, В. Т. (ред.), Недавний прогресс в комбинаторике, Academic Press, стр. 301–310, ISBN  978-0-12-705150-5.
• Шайнерман, Э. (1984), Классы пересечений и множественные параметры пересечений, Докторская диссертация, Принстонский университет.
• Томассен, Карстен (1986), «Интервальные представления плоских графов», Журнал комбинаторной теории, серия B, 40: 9–20, Дои:10.1016/0095-8956(86)90061-4.
• Яннакакис, Михалис (1982), "Сложность проблемы размерности частичного порядка", Журнал SIAM по алгебраическим и дискретным методам, 3 (3): 351–358, Дои:10.1137/0603036.