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

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

Свойства

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

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

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

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

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

Приложения

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

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

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

Свободные от биклик графы используются в теории параметрической сложности для разработки алгоритмов, эффективных для разреженных графов с достаточно малыми входными параметрами. В частности, поиск доминирующего множества размером k на свободных от t-биклик графах является фиксированно-параметрически разрешимой задачей, если использовать параметр k + t, даже хотя существуют веские основания, что это невозможно, если использовать только параметр k без t. Те же результаты верны для многих вариантов задачи о доминирующем множестве. Проверка, имеет ли доминирующее множество размер не более k, может быть также преобразована в другую проверку с той же параметризацией путём цепочки вставок и удалений вершин, сохраняя свойство доминирования.

Литература

• 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.