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

Перейти к навигацииПерейти к поиску

В теории графов свободный от 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. ↑ 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.