Інтервальна розмірність графа

У теорії графів інтервальна розмірність графа — це інваріант графа, введений Фредом С. Робертсом у 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].

Примітки
  1. Roberts, 1969.
  2. Наприклад, див. статті Чандрана, Френсіса і Сівадасана (Chandran, Francis, Sivadasan, (2010)), Чандрана і Сівадасана Chandran, Sivadasan, (2007).
  3. Scheinerman, 1984.
  4. Thomassen, 1986.
  5. Bellantoni, Hartman, Przytycka, Whitesides, 1993.
  6. Чандран, Френсіс і Сівадасан (Chandran, Francis, Sivadasan, (2010)) зауважили, що це випливає з факту, що ці графи мають поліноміальне число максимальних клік. Явне подання у вигляді перетину гіперпрямокутників не вимагає перерахування всіх максимальних клік.
  7. Див., наприклад, статті Agarwal, van Kreveld, Suri, (1998) і Berman, DasGupta, Muthukrishnan, Ramaswami, (2001) щодо апроксимації найбільшої незалежної множини для графів перетинів прямокутників, і Chlebík, Chlebíková, (2005) з обговоренням складності апроксимації цих задач для більших розмірностей.
  8. Коззенс (Cozzens, (1981)) показав, що обчислення інтервальної розмірності графа є NP-повною задачею. Яннакакіс (Yannakakis, (1982)) показав, що навіть перевірка, чи не перевищує інтервальна розмірність величини 3, є NP-складною. Нарешті, Краточвіл (Kratochvíl, (1994)) показав, що розпізнавання інтервальної розмірності = 2 є NP-складною задачею.
  9. Chandran, Francis, Sivadasan, 2010.
  10. 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.[недоступне посилання з червня 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 (3 березня). — С. 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 (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 (3 березня). — С. 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 (3 березня). — С. 129–140. — arXiv:cs.DM/0605013. — DOI:10.1007/s00453-008-9163-5.
  • L. Sunil Chandran, Naveen Sivadasan. Boxicity and treewidth // Journal of Combinatorial Theory. — 2007. — Т. 97, вип. 5 (3 березня). — С. 733–744. — (Series B). — arXiv:math.CO/0505544. — DOI:10.1016/j.jctb.2006.12.004.
  • 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 (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 (3 березня). — С. 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 (3 березня). — С. 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 (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 (3 березня). — С. 1687—1698. — DOI:10.1137/100786290.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.