Інтервальна розмірність графа
У теорії графів інтервальна розмірність графа — це інваріант графа, введений Фредом С. Робертсом у 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] описали алгоритми знаходження подань довільних графів у вигляді графа перетинів гіперпрямокутників з розмірністю в межах логарифмічного множника найбільшого степеня графа. Цей результат дає верхню межу інтервальної розмірності графа.
Попри труднощі для природних параметрів, інтервальна розмірність графа є фіксовано-параметрично розв'язною задачею[en], якщо параметризацію проводити за числом вершинного покриття вхідного графа[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:[недоступне посилання з червня 2018]
- 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 (2 квітня). — С. 209–218. — DOI:.
- Stephen J. Bellantoni, Irith Ben-Arroyo Hartman, Teresa Przytycka, Sue Whitesides. Grid intersection graphs and boxicity // Discrete Mathematics. — 1993. — Т. 114, вип. 1–3 (2 квітня). — С. 41–49. — DOI:.
- Piotr Berman, B. DasGupta, S. Muthukrishnan, S. Ramaswami. Efficient approximation algorithms for tiling and packing problems with rectangles // J. Algorithms. — 2001. — Т. 41, вип. 2 (2 квітня). — С. 443–47. — DOI:.
- L. Sunil Chandran, Mathew C. Francis, Naveen Sivadasan. Geometric representation of graphs in low dimension using axis parallel boxes // Algorithmica. — 2010. — Т. 56, вип. 2 (2 квітня). — С. 129–140. — arXiv:cs.DM/0605013. — DOI:.
- L. Sunil Chandran, Naveen Sivadasan. Boxicity and treewidth // Journal of Combinatorial Theory. — 2007. — Т. 97, вип. 5 (2 квітня). — С. 733–744. — (Series B). — arXiv:math.CO/0505544. — DOI:.
- 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 (2 квітня). — С. 233–252. — DOI:.
- M. Quest, G. Wegner. Characterization of the graphs with boxicity ≤ 2 // Discrete Mathematics. — 1990. — Т. 81, вип. 2 (2 квітня). — С. 187–192. — DOI:.
- 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 (2 квітня). — С. 9–20. — DOI:.
- Mihalis Yannakakis. The complexity of the partial order dimension problem // SIAM Journal on Algebraic and Discrete Methods. — 1982. — Т. 3, вип. 3 (2 квітня). — С. 351–358. — DOI:.
- Diptendu Bhowmick, L. Sunil Chandran, Abhijin Adiga. Boxicity and Poset Dimension // SIAM Journal on Discrete Mathematics. — 2011. — Т. 25, вип. 4 (2 квітня). — С. 1687—1698. — DOI:.