Главная
Статьи





01.07.2022


01.07.2022


01.07.2022


01.07.2022


01.07.2022






Ограниченное расширение графа

21.01.2022

Говорят, что семейство графов имеет ограниченное расширение, если все его миноры ограниченной глубины являются редкими графами. Много естественных семейств редких графов имеют ограниченное расширение. Близкое, но более сильное свойство, полиномиальное расширение, эквивалентно существованию теорем разбиения для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы для задач, в которые входят задача поиска изоморфного подграфа и проверка моделей для теории первого порядка для графов.

Определение и эквивалентные описания

Минор глубины t графа G определяется как граф, образованный из G путём стягивания набора не имеющих общих вершин подграфов радиуса t и удаления оставшихся вершин. Семейство графов имеет ограниченное расширение, если существует функция f, такая, что для любого минора глубины t графа из семейства отношение числа рёбер к числу вершин не превосходит f(t).

Другое определение классов ограниченного расширения — все миноры ограниченной глубины имеют хроматическое число, ограниченное некоторой функцией от t, или заданное семейство имеет ограниченное значение топологического параметра. Таким параметром является инвариант графа, монотонный относительно операции взятия подграфа, такой, что значение параметра может меняться только контролируемым способом, когда граф делится, и из ограниченности значения параметра следует, что граф имеет ограниченную вырожденность.

Полиномиальное расширение и теоремы о разбиении

Более строгое понятие — полиномиальное расширение, означающее, что функция f, используемая для ограничения плотности рёбер миноров ограниченной глубины, полиномиальна. Если наследуемое семейство графов удовлетворяет теореме о разбиении, утверждающей, что любой граф с n вершинами в семействе может быть разбит на две части, содержащие не более n/2 вершин, путём удаления O(nc) вершин для некоторой константы c < 1, то это семейство обязательно имеет полиномиальное расширение. Обратно — графы с полиномиальным расширением имеют теоремы с сублинейным сепаратором.

Классы графов с ограниченным расширением

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

Хотя графы ограниченной книжной ширины не содержат подлинейных сепараторов, они также имеют ограниченное расширение. В класс графов с ограниченным расширением входят графы ограниченной степени, случайные графы ограниченной средней степени в модели Эрдёша — Реньи и графы с ограниченным числом очередей.

Алгоритмические приложения

Экземпляр задачи изоморфизма подграфа, в которой целью является поиск графа ограниченного размера, являющегося подграфом большего графа, размер которого не ограничен, может быть решён за линейное время, если больший граф принадлежит семейству графов с ограниченным расширением. То же самое верно для поиска клик фиксированного размера, поиска доминирующих множеств фиксированного размера, или, более общего случая, проверки свойств, которые могут быть выражены формулой ограниченного размера в логике графов первого порядка.

Для графов с полиномиальным расширением существуют приближенные схемы полиномиального времени для задачи о покрытии множества, задачи о максимальном независимом множестве, задачи о доминирующем множестве и некоторые другие связанные задачи оптимизации.