В теории графов свободный от t - биклик граф — это граф, в котором нет полных двудольных графов с 2 t вершинами 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 : .
• 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. — ( ). — doi : .
• Haim Kaplan, Jiří Matoušek, Micha Sharir. Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique // . — 2012. — Т. 48 , вып. 3 . — С. 499–517 . — doi : . — arXiv : . . 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 : .