Интервальная размерность графа
В теории графов интервальная размерность графа — это инвариант графа, введённый Фредом С. Робертсом в 1969.
Интервальная размерность графа — это минимальная размерность, в которой заданный граф может быть представлен в виде графа пересечений гиперпрямоугольников (то есть многомерных прямоугольных параллелепипедов) с параллельными осям рёбрами. То есть должно существовать один-к-одному соответствие между вершинами графа и множеством гиперпрямоугольников, таких, что прямоугольники пересекаются тогда и только тогда, когда существует ребро, соединяющее соответствующие вершины.
Примеры
[править | править код]На фигуре показан граф с шестью вершинами и представление этого графа в виде графа пересечений (обычных двумерных) прямоугольников. Этот граф нельзя представить в виде графа пересечений прямоугольников меньшей размерности (в данном случае — отрезков), так что интервальная размерность графа равна двум.
Робертс[1] показал, что граф с 2n вершинами, образованный удалением совершенного паросочетания из полного графа с 2n вершинами, имеет интервальную размерность в точности n — любая пара несоединённых вершин должна быть представлена в виде гиперпрямоугольников, которые должны быть разделены в отличной от другой пары размерности. Представление этого графа в виде гиперпрямоугольников с размерностью в точности n можно найти путём утолщения каждой из 2n граней n-мерного гиперкуба в гиперпрямоугольник. Вследствие этого результата такие графы начали называться графами Робертса[2], хотя они более известны как графы «вечеринки» и их можно трактовать также как графы Турана T(2n,n).
Связь с другими классами графов
[править | править код]Граф имеет интервальную размерность не больше единицы тогда и только тогда, когда он является интервальным графом. Интервальная размерность произвольного графа G — это минимальное число интервальных графов с тем же множеством вершин (что и у G), таких, что пересечение множеств рёбер интервальных графов даёт G. Любой внешнепланарный граф имеет интервальную размерность, не превосходящую двух[3], а любой планарный граф имеет интервальную размерность, не превосходящую трёх [4].
Если двудольный граф имеет интервальную размерность два, его можно представить в виде графа пересечений параллельных осям отрезков на плоскости[5].
Алгоритмические результаты
[править | править код]Многие задачи на графах могут быть решены или аппроксимированы более эффективно на графах с ограниченной интервальной размерностью. Например, задача о наибольшей клике может быть решена за полиномиальное время для графов с ограниченной интервальной размерностью[6]. Для некоторых других задач на графах эффективное решение или аппроксимация могут быть найдены, если известно представление в виде пересечения гипермногогранников малой размерности [7].
Однако нахождение таких представлений может оказаться трудным делом — проверка, не превосходит ли интервальная размерность заданного графа некоторой наперёд заданной величины K, является NP-полной задачей, даже для K = 2[8]. Чандран, Фрэнсис и Сивадасан [9] описали алгоритмы для нахождения представлений произвольных графов в виде графа пересечений гиперпрямоугольников с размерностью, которая находится в пределах логарифмического множителя наибольшей степени графа. Этот результат даёт верхнюю границу интервальной размерности графа.
Несмотря на трудность для естественных параметров, интервальная размерность графа является фиксированно-параметрически разрешимой задачей[англ.], если параметризацию проводить по числу вершинного покрытия входного графа[10].
Примечания
[править | править код]- ↑ Roberts, 1969.
- ↑ Например, см. статьи Чандрана, Фрэнсиса и Сивадасана (Chandran, Francis, Sivadasan (2010)), Чандрана и Сивадасана Chandran, Sivadasan (2007).
- ↑ Scheinerman, 1984.
- ↑ Thomassen, 1986.
- ↑ Bellantoni, Hartman, Przytycka, Whitesides, 1993.
- ↑ Чандран, Фрэнсис и Сивадасан (Chandran, Francis, Sivadasan (2010)) заметили, что это следует из факта, что эти графы имеют полиномиальное число максимальных клик. Явное представление в виде пересечения гиперпрямоугольников не требует перечисления всех максимальных клик.
- ↑ См., например, статьи Agarwal, van Kreveld, Suri (1998) и Berman, DasGupta, Muthukrishnan, Ramaswami (2001) для аппроксимациям наибольшего независимого множества для графов пересечений прямоугольников, и Chlebík, Chlebíková (2005) для обсуждения сложности аппроксимации этих задач для больших размерностей
- ↑ Коззенс (Cozzens (1981)) показал, что вычисление интервальной размерности графа является NP-полной задачей. Яннакакис (Yannakakis (1982)) показал, что даже проверка, не превосходит ли интервальная размерность величины 3, является NP-трудной. Наконец, Краточвил (Kratochvíl (1994)) показал, что распознавание интервальной размерности = 2 является NP-трудной задачей.
- ↑ Chandran, Francis, Sivadasan, 2010.
- ↑ Adiga, Chitnis, Saurabh, 2010.
Литература
[править | править код]- Abhijin Adiga, Rajesh Chitnis, Saket Saurabh. Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I. — 2010. — Т. 6506. — С. 366–377. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-17517-6_33. (недоступная ссылка)
- Pankaj K. Agarwal, Marc van Kreveld, Subhash Suri. Label placement by maximum independent set in rectangles // Computational Geometry Theory and Applications. — 1998. — Т. 11, вып. 3–4. — С. 209–218. — doi:10.1016/S0925-7721(98)00028-5.
- Stephen J. Bellantoni, Irith Ben-Arroyo Hartman, Teresa Przytycka, Sue Whitesides. Grid intersection graphs and boxicity // Discrete Mathematics. — 1993. — Т. 114, вып. 1–3. — С. 41–49. — doi:10.1016/0012-365X(93)90354-V.
- Piotr Berman, B. DasGupta, S. Muthukrishnan, S. Ramaswami. Efficient approximation algorithms for tiling and packing problems with rectangles // J. Algorithms. — 2001. — Т. 41, вып. 2. — С. 443–47. — doi:10.1006/jagm.2001.1188.
- L. Sunil Chandran, Mathew C. Francis, Naveen Sivadasan. Geometric representation of graphs in low dimension using axis parallel boxes // Algorithmica. — 2010. — Т. 56, вып. 2. — С. 129–140. — doi:10.1007/s00453-008-9163-5. — arXiv:cs.DM/0605013.
- L. Sunil Chandran, Naveen Sivadasan. Boxicity and treewidth // Journal of Combinatorial Theory. — 2007. — Т. 97, вып. 5. — С. 733–744. — doi:10.1016/j.jctb.2006.12.004. — arXiv:math.CO/0505544.
- Miroslav Chlebík, Janka Chlebíková. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — 2005. — С. 267–276.
- M. B. Cozzens. Higher and Multidimensional Analogues of Interval Graphs. — Rutgers University, 1981. — (Ph.D. thesis).
- Jan Kratochvíl. A special planar satisfiability problem and a consequence of its NP–completeness // Discrete Applied Mathematics. — 1994. — Т. 52, вып. 3. — С. 233–252. — doi:10.1016/0166-218X(94)90143-0.
- M. Quest, G. Wegner. Characterization of the graphs with boxicity ≤ 2 // Discrete Mathematics. — 1990. — Т. 81, вып. 2. — С. 187–192. — doi:10.1016/0012-365X(90)90151-7.
- F. S. Roberts. Recent Progress in Combinatorics / W. T. Tutte. — Academic Press, 1969. — С. 301–310. — ISBN 978-0-12-705150-5.
- E. R. Scheinerman. Intersection Classes and Multiple Intersection Parameters. — Princeton University, 1984. — (Ph. D thesis).
- Carsten Thomassen. Interval representations of planar graphs // Journal of Combinatorial Theory, Series B. — 1986. — Т. 40. — С. 9–20. — doi:10.1016/0095-8956(86)90061-4.
- Mihalis Yannakakis. The complexity of the partial order dimension problem // SIAM Journal on Algebraic and Discrete Methods. — 1982. — Т. 3, вып. 3. — С. 351–358. — doi:10.1137/0603036.
- Diptendu Bhowmick, L. Sunil Chandran, Abhijin Adiga. Boxicity and Poset Dimension // SIAM Journal on Discrete Mathematics. — 2011. — Т. 25, вып. 4. — С. 1687—1698. — doi:10.1137/100786290.
 | Для улучшения этой статьи желательно:
|