Вільний від біклік граф

У теорії графів ві́льний від t-біклі́к граф — граф, у якому немає повних двочасткових графів із 2t вершинами Kt,t як підграфів. Сімейство графів є вільним від біклік, якщо існує число t таке, що всі графи в сімействі вільні від t-біклік. Сімейства вільних від біциклів графів утворюють один із найзагальніших типів сімейств розріджених графів. Вони виникають у задачах інцидентності в комбінаторній геометрії, а також використовуються в теорії параметричної складності[en].

Властивості

Розрідженість

За теоремою Коварі — Сос — Турана, будь-який вільний від t-біциклів граф із n вершинами має O(n2 − 1/t) ребер, тобто, граф істотно рідкший, ніж щільний граф[1]. З іншого боку, якщо сімейство графів визначене забороненими підграфами або замкнуте відносно операції взяття підграфа і не включає щільних графів довільно великого розміру, воно має бути вільним від t-біклік для деякого t, інакше, сімейство має включати довільно великі щільні повні двочасткові графи.

Щодо нижньої межі Ердеш, Хайнал і Муун[2] висловили припущення, що будь-який максимальний вільний від t-біклік двочастковий граф (до якого не можна додати ребро без створення t-бікліки) має принаймні (t − 1)(n + m − t + 1) ребер, де n та m — число вершин у кожній частці графа[3].

Зв'язок з іншими типами сімейств розріджених графів

Граф із виродженням d є обов'язково вільним від (d + 1)-біклік. Крім того, сімейство вільних від бікліків графів має бути ніде не щільним, що означає, що для будь-якого числа k існує граф, який не є k-неглибоким мінором будь-якого графа зі сімейства. Зокрема, якщо існує граф з n вершинами, який не є 1-неглибокими мінором, то сімейство має бути вільним від n-біклік, оскільки всі графи з n вершинами є 1-неглибокими мінорами графа Kn,n. Отже, вільні від біклік сімейства графів уніфікують два з найзагальніших класів розріджених графів[4].

Застосування

Дискретна геометрія

У комбінаторній геометрії багато типів графів інцидентності завідомо вільні від біклік. Наприклад, граф інцидентності скінченної множини точок і прямих на евклідовій площині завідомо не містить підграфа K2,2[5].

Параметризована складність

Вільні від біклік графи використовують у теорії параметризованої складності[en] для розробки алгоритмів, ефективних для розріджених графів із досить малими вхідними параметрами. Зокрема, пошук домінівної множини розміром k на вільних від t-біклік графах є фіксовано-параметризовано розв'язною задачею, якщо використати параметр k + t, навіть попри те, що існують вагомі підстави, що це неможливо, якщо використовувати тільки параметр k без t. Ті ж результати істинні для багатьох варіантів задачі про домінівну множину[4]. Перевірка, чи має домінівна множина розмір не більше k можна також перетворити на іншу перевірку з тією ж параметризацією застосуванням низки вставок і видалень вершин, зберігаючи властивість домінування[6].

Примітки

  1. ↑ Kővári, T. Sós, Turán, 1954. Ця праця розглядає число ребер вільних від біклік графів, але стандартне застосування ймовірнісного методу переносить ті самі межі на довільні графи.
  2. ↑ Erdős, Hajnal, Moon, 1964.
  3. ↑ Erdős, Hajnal, Moon, 1964, с. 1107–1110.
  4. ↑ а б Telle, Villanger, 2012, с. 802–812.
  5. ↑ Kaplan, Matoušek, Sharir, 2012, с. 499–517.
  6. ↑ Lokshtanov, Mouawad, Panolan, Ramanujan, Saurabh, 2015, с. 506–517.

Література

  • T. Kővári, V. T. Sós, P. Turán. On a problem of K. Zarankiewicz // Colloquium Math.. — 1954. — Т. 3. — С. 50–57.
  • P. Erdős, A. Hajnal, J. W. Moon. A problem in graph theory // The American Mathematical Monthly. — 1964. — Т. 71. — С. 1107–1110. — DOI:10.2307/2311408.
  • Jan Arne Telle, Yngve Villanger. Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings / Leah Epstein, Paolo Ferragina. — Springer, 2012. — Т. 7501. — С. 802–812. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-33090-2_69.
  • Haim Kaplan, Jiří Matoušek, Micha Sharir. Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique // Discrete and Computational Geometry. — 2012. — Т. 48, вип. 3. — С. 499–517. — arXiv:1102.5391. — DOI:10.1007/s00454-012-9443-3.. Дивіться, зокрема, лему 3.1 і зауваження після леми.
  • Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan, Saket Saurabh. Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings / Frank Dehne, Jörg-Rüdiger Sack, Ulrike Stege. — Springer, 2015. — Т. 9214. — С. 506–517. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-319-21840-3_42.