Свободный от биклик граф

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Разреженность

[править | править код]

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

В качестве нижней границы Эрдёш, Хайнал и Муун[2] высказали предположение, что любой максимальный свободный от t-биклик двудольный граф (к которому нельзя добавить ребро без создания t-биклики) имеет по меньшей мере (t − 1)(n + mt + 1) рёбер, где n и m — число вершин на каждой из долей графа[3].

Связь с другими типами семейств разреженных графов

[править | править код]

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

Приложения

[править | править код]

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

[править | править код]

В комбинаторной геометрии многие типы графов инцидентности заведомо свободны от биклик. В качестве простого примера граф инцидентности конечного множества точек и прямых на евклидовой плоскости заведомо не содержит K2,2 подграфа[5].

Параметризованная сложность

[править | править код]

Свободные от биклик графы используются в теории параметрической сложности[англ.] для разработки алгоритмов, эффективных для разреженных графов с достаточно малыми входными параметрами. В частности, поиск доминирующего множества размером 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. 1 2 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. — doi:10.1007/s00454-012-9443-3. — arXiv:1102.5391.. See in particular Lemma 3.1 and the remarks following the lemma.
  • 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.