В теории графов говорят , что семейство графов имеет ограниченное расширение , если все его мелкие миноры являются разреженными графами . Многие естественные семейства разреженных графов имеют ограниченное расширение. Тесно связанное, но более сильное свойство, полиномиальное разложение , эквивалентно существованию теорем о разделителе для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы для решения проблем, включая проблему изоморфизма подграфов и проверку моделей для теории графов первого порядка.
t -мелкий минор графа G определяется как граф, сформированный из G путем сжатия набора непересекающихся по вершинам подграфов радиуса t и удаления оставшихся вершин G . Семейство графов имеет ограниченное расширение, если существует функция f такая, что в каждом t -мелком миноре графа в семействе отношение ребер к вершинам не превосходит f ( t ). [1]
Эквивалентные определения классов ограниченных расширений заключаются в том, что все мелкие миноры имеют хроматическое число , ограниченное функцией t , [1] или что данное семейство имеет ограниченное значение топологического параметра . Такой параметр представляет собой инвариант графа , монотонный относительно подграфов, такой, что значение параметра может изменяться только контролируемым образом при подразделении графа, и такой, что ограниченное значение параметра подразумевает, что граф имеет ограниченное вырождение . [2]
Более сильное понятие – полиномиальное разложение , означающее, что функция f, используемая для ограничения плотности ребер мелких миноров, является полиномом . Если семейство наследственных графов подчиняется теореме о разделителе , утверждающей, что любой n -вершинный граф в семействе можно разбить на части с не более чем n /2 вершинами путем удаления O ( n c ) вершин для некоторой константы c < 1, то это семейство обязательно имеет полиномиальное расширение. И наоборот, графы с полиномиальным разложением имеют теоремы о сублинейном разделителе. [3]
Из-за связи между разделителями и расширением каждое минорно-замкнутое семейство графов , включая семейство планарных графов , имеет полиномиальное расширение. То же самое верно для 1-планарных графов и, в более общем смысле, для графов, которые можно встроить в поверхности ограниченного рода с ограниченным числом пересечений на ребро, а также для струнных графов без биклик , поскольку все они подчиняются аналогичным теоремам о сепараторах. к планарным графам. [4] [5] [6] [ 7 ] В евклидовых пространствах более высокой размерности графы пересечений систем шаров со свойством, что любая точка пространства покрывается ограниченным числом шаров, также подчиняются теоремам о сепараторах [8] , которые подразумевают полиномиальность расширение.
Хотя графы ограниченной толщины книги не имеют сублинейных разделителей, [9] они также имеют ограниченное расширение. [10] Другие графы ограниченного расширения включают графы ограниченной степени, [11] случайные графы ограниченной средней степени в модели Эрдеша – Реньи , [12] и графы ограниченного числа очередей . [2] [13]
Примеры проблемы изоморфизма подграфов , цель которой состоит в том, чтобы найти целевой граф ограниченного размера как подграф большего графа, размер которого не ограничен, могут быть решены за линейное время , когда больший граф принадлежит семейству графов ограниченное расширение. То же самое верно для поиска клик фиксированного размера, поиска доминирующих наборов фиксированного размера или, в более общем плане, проверки свойств, которые могут быть выражены формулой ограниченного размера в логике графов первого порядка . [14] [15]
Для графов полиномиального расширения существуют схемы аппроксимации полиномиального времени для задачи покрытия множества , задачи максимального независимого множества , задачи доминирующего множества и нескольких других связанных задач оптимизации графа. [16]