Алгоритм поиска декомпозиции с малой древовидной шириной

Продолжая развивать эти идеи, мы приведем жадный алгоритм для построения древовидной декомпозиции низкой ширины.

лгоритм не будет точно определять древовидную ширину входного графа G = (V, E); вместо этого он по заданному параметру w либо строит декомпозицию ширины менее 4w, либо обнаруживает (w + 1)-связное множество с размером не менее 3w.

Как упоминалось ранее, время выполнения определяется в форме O( f (w) · mn), где m и n — количество ребер и узлов G, а f (·) зависит только от w.

С некоторым опытом работы с декомпозициями можно представить себе, что может потребоваться для построения декомпозиции для произвольного входного графа G.

Наша цель — заставить G распасться на древовидные части; декомпозиция начинается с размещения первого фрагмента Vt в любом месте.

Если повезет, G − Vt состоит из нескольких изолированных компонент; мы рекурсивно заходим в каждую компоненту и размещаем в ней фрагмент так, чтобы он частично перекрывал уже определенный фрагмент Vt.

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

Ключевую роль в работе этого алгоритма играет следующий факт: если в какой-то момент мы окажемся в тупике и наши малые множества не приведут к дальнейшему разбиению графа, можно будет извлечь большое (w + 1)-связное множество, которое докажет, что древовидная ширина на самом деле была большой.