Інтервальна розмірність графа
У теорії графів інтервальна розмірність графу — це інваріант графу, введений Фредом С. Робертсом у 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.
- ↑ Наприклад, див. статті Чандрана, Френсіса і Сівадасана (Помилка скрипту: Функції «harvard_core» не існує.), Чандрана і Сівадасана Помилка скрипту: Функції «harvard_core» не існує..
- ↑ Scheinerman, 1984.
- ↑ Thomassen, 1986.
- ↑ Bellantoni, Hartman, Przytycka, Whitesides, 1993.
- ↑ Чандран, Френсіс і Сівадасан (Помилка скрипту: Функції «harvard_core» не існує.) зауважили, що це випливає з факту, що ці графи мають поліноміальне число максимальних клік. Явне подання у вигляді перетину гіперпрямокутників не вимагає перерахування всіх максимальних клік.
- ↑ Див., наприклад, статті Помилка скрипту: Функції «harvard_core» не існує. і Помилка скрипту: Функції «harvard_core» не існує. щодо апроксимації найбільшої незалежної множини для графів перетинів прямокутників, і Помилка скрипту: Функції «harvard_core» не існує. з обговоренням складності апроксимації цих задач для більших розмірностей.
- ↑ Коззенс (Помилка скрипту: Функції «harvard_core» не існує.) показав, що обчислення інтервальної розмірності графу є NP-повною задачею. Яннакакіс (Помилка скрипту: Функції «harvard_core» не існує.) показав, що навіть перевірка, чи не перевищує інтервальна розмірність величини 3, є NP-складною. Нарешті, Краточвіл (Помилка скрипту: Функції «harvard_core» не існує.) показав, що розпізнавання інтервальної розмірності = 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:.