Концепция использования свойств, которыми граф обладает локально, может быть взята еще дальше. Давар, Гроэ и Кройцер в Локально исключая минор рассматривал классы графов, которые локально исключают минор, а Дворжак, Крал и Томас в Решении свойств первого порядка для разреженных графов рассматривали классы графов, которые имеют (локально) ограниченное расширение.
Оба эти класса относятся к классам нигде не плотных графов, введенных Несетриль и Оссона де Мендес.
Grohe объявил на этой неделе на конференции Highlights, что Grohe, Kreutzer и Siebertz. доказали, что каждое свойство графов, определяемых в логике первого порядка, может быть решено за почти линейное время на нигде не плотных классах графов. Это подразумевает множество результатов проходимости с фиксированными параметрами на нигде не плотных графах, например, для (связного) доминирующего множества и ядра орграфа (оба параметризованы размером решения), дерева Штейнера (параметризованного размера дерева) и выполнимости схемы ( параметризованный глубиной контура и весом решения по Хэммингу).
Себастьян Сибертц
источник