Декомпозиция графа на ветви

Некорневое бинарное дерево — это связный неориентированный граф без циклов, в котором каждый нелистовой узел имеет в точности три соседа. Декомпозиция на ветви может быть представлена как некорневое бинарное дерево T вместе с биекцией между листьями дерева T и рёбрами заданного графа G = (V,E). Если e — любое ребро дерева T, то удаление e из T делит его на два поддерева T₁ и T₂. Это разделение дерева T на поддеревья порождает разделение рёбер, ассоциированных с листьями дерева T, на два подграфа графа G, G₁ и G₂. Такое деление графа G на два подграфа называется e-разделением.

Ширина e-разделения — это число вершин графа G, которые инцидентны как рёбрам из E₁, так и рёбрам из E₂. То есть это множество вершин, общих для подграфов G₁ и G₂. Ширина декомпозиции на ветви — это максимальная ширина любого e-разделения. Ширина ветвления графа G — это минимальная ширина декомпозиций по ветвям графа G.

Декомпозиция графа на ветви тесно связана с древесной декомпозицией, а ширина ветвления тесно связана с древесной ширине. Две эти величины отличаются не более чем на постоянный множитель. В частности, в статье, в которой они предложили ширину ветвления, Нейл Робертсон и Пол Сеймур[1] показали, что для графа G с древесной шириной k и шириной ветвления b > 1

${\displaystyle b-1\leq k\leq \left\lfloor {\frac {3}{2}}b\right\rfloor -1.}$

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

Алгоритмы определения ширины ветвления обычно работают путём сведения к эквивалентной задаче определения ширины нарезки. В частности, ширина нарезки срединного графа в точности вдвое больше ширины ветвления исходного графа[2].

Задача определения, имеет ли граф G декомпозицию на ветви с шириной, не превосходящей k, является NP-полной, если G и k являются входными данными задачи[2]. Однако графы с шириной ветвления не большей k, образуют семейство графов, замкнутое по минорам[3], откуда следует, что вычисление ширины ветвления является фиксированно-параметрически разрешимой задачей: существует алгоритм для вычисления оптимальной декомпозиции на ветви, время работы которого на графах с шириной ветвления, не превосходящей k для некоторой постоянной k, линейно зависит от размера графа[4]

Для планарных графов ширина ветвления может быть вычислена за линейное время. Это контрастирует с древесной шириной, для которой сложность вычисления на планарных графах является хорошо известной открытой проблемой[5]. Исходный алгоритм вычисления ширины ветвления для планарных графов Пола Сеймура и Робина Томаса решал задачу за время O(n²) на графе с n вершинами, а их алгоритм для построения декомпозиции на ветви работал за время O(n⁴)[2]. Позднее последний был улучшен до O(n³)[6].

Как и в случае древесной ширины, ширина ветвления может быть использована в качестве базиса алгоритмов динамического программирования для многих NP-трудных задач оптимизации, и в этих алгоритмах время решения будет экспоненциальным от ширины входного графа или матроида[7][8]. Например, Кук и Сеймур[9] применили основанный на ширине ветвления метод динамического программирования к задаче слияния частичных решений задачи коммивояжёра в одно глобальное решение путём формирования разреженного графа из объединения частичных решений, для чего использовалась эвристическая спектральная кластеризация для нахождения хорошей декомпозиции на ветви, после чего к полученной декомпозиции они применили динамическое программирование. Фомин и Тиликос[10] убеждают, что ширина ветвления работает лучше, чем древесная ширина, при разработке фиксированно-параметрически разрешимых алгоритмов на планарных графах по многим причинам — ширина ветвления может быть теснее ограничена функцией параметра, чем ограничение древесной ширины, она может быть вычислена за полиномиальное время и алгоритм вычисления ширины ветвления не имеет больших скрытых констант.

Можно также определить понятие декомпозиции по ветвям для матроидов, что обобщает декомпозицию графов по ветвям[11]. Декомпозиция матроида по ветвям является иерархической кластеризацией элементов матроида, представленная как некорневое бинарное дерево с элементами матроида в качестве листьев. Для матроидов e-разделение можно определить тем же способом, что и для графов, а в результате получаем разделения множества M элементов матроида на два подмножества A и B. Если через ρ обозначить функцию ранга матроида, то ширина e-разделения определяется как ρ(A) + ρ(B) − ρ(M) + 1, а ширина декомпозиции и ширина ветвления матроида определяются аналогично определениям для графа. Ширина ветвления графа и ширина ветвления соответствующего графового матроида могут отличаться. Например, путь из трёх рёбер и звезда из трёх рёбер имеют разные ширины ветвления, 2 и 1 соответственно, но для них графовый матроид один и тот же, и он имеет ширину ветвления 1[12]. Однако для графов, не являющихся деревьями, ширина ветвления графа равна ширине ветвления ассоциированного графового матроида[12][13]. Ширина ветвления матроида равна ширине ветвления его двойственного матроида, и из этого в частности следует, что ширина ветвления любого планарного графа, не являющегося деревом, равна ширине ветвления его двойственного графа[12].

Ширина ветвления является важной компонентой попыток расширить теорию миноров графа на миноры матроидов — хотя древесная ширина может быть также обобщена на матроиды[14] и играет в теории миноров графов бо́льшую роль, чем ширина ветвления, ширина ветвления имеет более удобные свойства в матроидах[15]. Робертсон и Сеймур высказали предположение, что матроиды, представимые любым конкретным конечным полем, вполне квазиупорядоченны, что является аналогией теоремы Робертсона – Сеймура для графов, но гипотеза доказана только для матроидов с ограниченной шириной ветвления[16][15]. Кроме того, если семейство матроидов, замкнутое по минорам и представимое конечным полем, не включает графовые матроиды всех планарных графов, то существует постоянная, ограничивающая ширину ветвления в семействе, что обобщает соответствующее утверждение для семейств графов, замкнутых по минорам[15][17].

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

Четыре запрещённых минора для графов ширины ветвления три.

По теореме Робертсона — Сеймура графы с шириной ветвления k могут быть охарактеризованы конечным множеством запрещённых миноров. Графы с шириной ветвления 0 — это паросочетания, а минимальные запрещённые миноры в этом случае — это путь из двух дуг и треугольный граф (а также цикл из двух дуг, если рассматриваются мультиграфы)[19]. Графы с шириной ветвления 1 — это графы, в которых каждая связная компонента является звездой, а минимальные запрещённые миноры для графов с шириной ветвления 1 — это треугольный граф (или цикл из двух дуг, если рассматриваются мультиграфы) и пути из трёх дуг[19]. Графы с шириной ветвления 2 — это графы, в которых каждая двусвязная компонента является параллельно-последовательным графом, а единственным минимальным запрещённым минором является полный граф K₄ из четырёх вершин[19]. Граф имеет ширину ветвления три тогда и только тогда, когда его древесная ширина равна трём и он не имеет граф гиперкуба в качестве минора. Таким образом, четыре запрещённых минора — это три из четырёх запрещённых миноров графов с древесной шириной три (граф октаэдра, полный граф K₅, и граф Вагнера) вместе с графом куба[20].

Запрещённые миноры изучаются также и для ширины ветвления матроида, несмотря на отсутствие полной аналогии теоремы Робертсона — Сеймура в этом случае. Матроид имеет ширину ветвления единица тогда и только тогда, когда любой элемент является либо петлёй, либо копетлёй, так что единственным минимальным запрещённым минором является однородный матроид U(2,3), графовый матроид треугольного графа. Матроид имеет ширину ветвления два тогда и только тогда, когда он является графовым матроидом графа с шириной ветвления два, так что минимальными запрещёнными минорами являются графовые матроиды графа K₄ и неграфовый матроид U(2,4). Матроиды с шириной ветвления три не вполне квазиупорядоченны без дополнительного предположения представления над конечным полем, но, тем не менее, матроиды с любой ограниченной шириной ветвления имеют конечное число минимальных запрещённых миноров, которые имеют число элементов, зависящих от ширины ветвления не более чем экспоненциально[21][22].