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

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

Свойства

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

Согласно теореме Ковари – Сос – Турана любой свободный от 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].

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

Свободные от биклик графы используются в теории параметрической сложности для разработки алгоритмов, эффективных для разреженных графов с достаточно малыми входными параметрами. В частности, поиск доминирующего множества размером 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. — 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.