Гілкова декомпозиція
У теорії графів гілкова декомпозиція неорієнтованого графа G — це ієрархічна кластеризація ребер графа G, представлена некореневим двійковим деревом T з ребрами з G як листками. Видалення будь-якого ребра з T поділяє ребра графа G на два підграфи, а шириною декомпозиції вважають найбільшу кількість спільних вершин у будь-якому підграфі, отриманому в такий спосіб. Ширина галуження графа G це найменша ширина будь-якої гілкової декомпозиції графа G.
Ширина галуження тісно пов'язана з деревною шириною — для всіх графів вони лежать у межах сталого множника одна від одної, і обидві величини можна описати забороненими мінорами. Як і для деревної ширини, багато задач оптимізації на графах можна ефективно розв'язати на графах із малою шириною галуження. Проте, на відміну деревної ширини, ширину галуження планарного графа можна обчислити точно за поліноміальний час. Гілкову декомпозицію та ширину галуження можна узагальнити з графів на матроїди.
Некореневе двійкове дерево — це зв'язний неорієнтований граф без циклів, у якому кожен нелистовий вузол має рівно три сусіди. Гілкову декомпозицію можна подати як некореневе двійкове дерево T разом з бієкцією між листками дерева T та ребрами даного графа G = (V, E). Якщо e — будь-яке ребро дерева T, то видалення e з T ділить його на два піддерева T1 і T2. Цей поділ дерева T на піддерева породжує поділ ребер, асоційованих з листками дерева T на два підграфи графа G, G1 і G2. Такий поділ графа G на два підграфи називають e-поділом.
Ширина e-поділу — це число вершин графа G, інцидентних як ребрам з E1, так і ребрам з E2. Тобто це множина вершин, спільних для підграфів G1 і G2. Ширина гілкової декомпозиції — це найбільша ширина будь-якого e-поділу. Ширина галуження графа G — це найменша ширина гілкових декомпозицій графа G.
Гілкова декомпозиція графа тісно пов'язана з деревною декомпозицією, а ширина галуження тісно пов'язана з деревною шириною. Дві ці величини відрізняються лише сталим множником. Зокрема, в статті, в якій вони запропонували ширину галуження, Нейл Робертсон[en] і Пол Сеймур[ru][1] показали, що для графа G з деревною шириною k і шириною галуження b > 1
Ширина нарізки — це концепція, визначена аналогічно ширині галуження, з тією різницею, що у визначеннях вершини та ребра міняють місцями. Декомпозиція нарізкою — це некореневе двійкове дерево, в якому кожен листок представляє вершину початкового графа, а ширина розрізу — це число (або повна вага у зважених графах) ребер, інцидентних вершині в обох піддеревах.
Алгоритми визначення ширини галуження зазвичай працюють зведенням до еквівалентної задачі визначення ширини нарізки. Зокрема, ширина нарізки серединного графа рівно вдвічі більша за ширину галуження вихідного графа[2].
Задача визначення, чи має граф G гілкову декомпозицію із шириною, що не перевищує k, є NP-повною, якщо G і k є вхідними даними задачі[2]. Однак графи зі шириною галуження не більшою від k, утворюють сімейство графів, замкнене за мінорами[3], звідки випливає, що обчислення ширини галуження є фіксовано-параметрично розв'язною[en] задачею: існує алгоритм для обчислення оптимальної гілкової декомпозиції, час роботи якого на графах із шириною галуження, що не перевищує k для деякого сталого k, лінійно залежить від розміру графа[4].
Для планарних графів ширину галуження можна обчислити за лінійний час. Це контрастує із деревною шириною, для якої складність обчислення на планарних графах є добре відомою відкритою проблемою[5]. Початковий алгоритм Пола Сеймура і Робіна Томаса[en] для обчислення ширини галуження планарних графів розв'язував задачу за час O(n2) на графі з n вершинами, а їхній алгоритм для побудови гілкової декомпозиції працював за час O(n4)[2]. Пізніше останній покращено до O(n3)[6].
Як і в разі деревної ширини, ширину галуження можна використати як базис алгоритмів динамічного програмування для багатьох NP-складних задач оптимізації, і в цих алгоритмах час розв'язування буде експоненціальним від ширини вхідного графа або матроїда[7][8]. Наприклад, Кук і Сеймур[9] застосували заснований на ширині галуження метод динамічного програмування до задачі злиття часткових розв'язків задачі комівояжера в один глобальний розв'язок шляхом формування розрідженого графа з об'єднання часткових розв'язків, де використали евристичне спектральне кластерування для знаходження хорошої гілкової декомпозиції, після чого до неї застосували динамічне програмування. Фомін і Тілікос[10] запевняють, що при розробці фіксовано-параметрично розв'язуваних алгоритмів на планарних графах ширина галуження працює краще, ніж деревна ширина, з багатьох причин — ширина галуження може бути тісніше обмеженою функцією параметра, ніж обмеження деревної ширини, її можна обчислити за поліноміальний час і алгоритм обчислення ширини галуження не має великих прихованих констант.
Поняття гілкової декомпозиції можна також визначити для матроїдів, що узагальнює гілкову декомпозицію графів[11]. Гілкова декомпозиція матроїда є ієрархічною кластеризацією елементів матроїда, подана як некореневе двійкове дерево з елементами матроїда як листками. Для матроїдів e-поділ можна визначити в той самий спосіб, що й для графів, а результатом буде поділ множини M елементів матроїда на дві підмножини A і B. Якщо через ρ позначити функцію рангу матроїда, то ширина e-поділу визначається як ρ(A) + ρ(B) − ρ(M) + 1, а ширина декомпозиції та ширина галуження матроїда визначаються аналогічно до визначень для графа. Ширина галуження графа та ширина галуження відповідного графового матроїда[en] відрізняються. Наприклад, шлях із трьох ребер і зірка з трьох ребер мають різні ширини галуження, 2 і 1 відповідно, але графовий матроїд у них однаковий і має ширину галуження 1[12]. Однак для графів, що не є деревами, ширина галуження графа дорівнює ширині галуження пов'язаного графового матроїда[12][13]. Ширина галуження матроїда дорівнює ширині галуження його двоїстого матроїда[en], і з цього випливає, що ширина галуження будь-якого планарного графа, який не є деревом, дорівнює ширині галуження його двоїстого графа[12].
Ширина галуження — важлива складова спроб розширити теорію мінорів графа на мінори матроїдів[en] — хоча деревну ширину можна також узагальнити на матроїди[14] і її роль у теорії графів більша, ніж ширини галуження, ширина галуження має зручніші властивості[15]. Робертсон і Сеймур висловили припущення, що матроїди, подані будь-яким конкретним скінченним полем, цілком квазівпорядковані[en] , що є аналогією теореми Робертсона — Сеймура для графів, але гіпотезу доведено тільки для матроїдів із обмеженою шириною галуження[16][15]. Крім того, якщо сімейство матроїдів, замкнене за мінорами і подане скінченним полем, не включає графових матроїдів усіх планарних графів, існує стала, яка обмежує ширину галуження в сімействі, що узагальнює відповідне твердження для сімейств графів, замкнутих за мінорами[15][17].
Для будь-якого фіксованого k матроїди з шириною галуження, що не перевищує k, можна розпізнати за поліноміальний час алгоритмом, який отримує доступ до матроїда через оракула незалежності[en][18].
За теоремою Робертсона — Сеймура графи з шириною галуження k можна схарактеризувати скінченною множиною заборонених мінорів. Графи з шириною галуження 0 — це парування, а найменші заборонені мінори в цьому випадку — це шлях із двох дуг та трикутний граф (а також цикл із двох дуг, якщо розглядаються мультиграфи)[19]. Графи з шириною галуження 1 — це графи, в яких кожна компонента зв'язності є зіркою, а найменші заборонені мінори для графів з шириною галуження 1 — це трикутний граф (або цикл із двох дуг, якщо розглядаються мультиграфи) і шляхи з трьох дуг[19]. Графи з шириною галуження 2 — це графи, в яких кожна двозв'язна компонента є паралельно-послідовним графом, а єдиним найменшим забороненим мінором є повний граф K4 з чотирьох вершин[19]. Граф має ширину галуження три тоді й лише тоді, коли його деревна ширина дорівнює трьом і він не має мінором графа гіперкубу. Таким чином, чотири заборонені мінори — це три з чотирьох заборонених мінорів графів з деревною шириною три (граф октаедра, повний граф K5 і граф Вагнера) разом із графом куба[20].
Заборонені мінори вивчаються також і для ширини галуження матроїда, попри відсутність повної аналогії теореми Робертсона — Сеймура у цьому разі. Матроїд має ширину галуження одиниця тоді й лише тоді, коли будь-який елемент є або петлею, або копетлею, так що єдиним найменшим забороненим мінором є однорідний матроїд[en] U(2,3), графовий матроїд трикутного графа. Матроїд має ширину галуження два тоді й лише тоді, коли він є графовим матроїдом графа з шириною галуження два, так що мінімальними забороненими мінорами є графові матроїди графа K4 і неграфовий матроїд U(2,4). Матроїди з шириною галуження три не цілком квазівпорядковані без додаткового припущення щодо подання над скінченним полем, але, тим не менш, матроїди з будь-якою обмеженою шириною галуження мають скінченне число найменших заборонених мінорів, які мають число елементів, що залежать від ширини галуження не більш ніж експоненційно[21][22].
- ↑ Robertson, Seymour, 1991, с. 168, Theorem 5.1.
- ↑ а б в Seymour, Thomas, 1994.
- ↑ Robertson, Seymour, 1991, с. 164, Theorem 4.1.
- ↑ Bodlaender, Thilikos, (1997). Фомін, Мацойт і Тодінка Fomin, Mazoit, Todinca, (2009) описують алгоритм із покращеною залежністю від k, (2√3)k, але залежність від числа вершин зростає від лінійної до квадратичної.
- ↑ Kao, Ming-Yang, ред. (2008), Treewidth of graphs, Encyclopedia of Algorithms, Springer, с. 969, ISBN 9780387307701, архів оригіналу за 5 червня 2022, процитовано 5 червня 2022,
Ще одна давня відкрита проблема: Чи існує алгоритм поліноміального часу обчислення деревної ширини планарного графа?
- ↑ Gu, Tamaki, 2008.
- ↑ Hicks, 2000.
- ↑ Hliněný, 2003.
- ↑ Cook, Seymour, 2003.
- ↑ Fomin, Thilikos, 2006.
- ↑ Robertson, Seymour, 1991, с. 188–190, Section 12, «Tangles and Matroids».
- ↑ а б в Mazoit, Thomassé, 2007.
- ↑ Hicks, McMurray, 2007.
- ↑ Hliněný, Whittle, 2006.
- ↑ а б в Geelen, Gerards, Whittle, 2006.
- ↑ Geelen, Gerards, Whittle, 2002.
- ↑ Geelen, Gerards, Whittle, 2007.
- ↑ Oum, Seymour, 2007.
- ↑ а б в Robertson, Seymour, 1991, с. 165, Theorem 4.2.
- ↑ Bodlaender, Thilikos, (1999). Четвертий заборонений мінор для деревної ширини три, граф п'ятикутної призми, має граф куба як мінор, так що він не є найменшим для ширини галуження три.
- ↑ Hall, Oxley, Semple, Whittle, 2002.
- ↑ Geelen, Gerards, Robertson, Whittle, 2003.
- Hans L. Bodlaender, Dimitrios M. Thilikos. Proc. 24th International Colloquium on Automata, Languages and Programming (ICALP '97). — Springer-Verlag, 1997. — Т. 1256. — С. 627–637. — (Lecture Notes in Computer Science) — DOI:
- Hans L. Bodlaender, Dimitrios M. Thilikos. Graphs with branchwidth at most three // Journal of Algorithms. — 1999. — Т. 32, вип. 2. — С. 167—194. — DOI:.
- William, Paul D. Seymour. Tour merging via branch-decomposition // INFORMS Journal on Computing. — 2003. — Т. 15, вип. 3. — С. 233—248. — DOI:. Архівовано з джерела 31 липня 2010. Процитовано 5 червня 2022..
- Fedor V. Fomin, Dimitrios M. Thilikos. Dominating sets in planar graphs: branch-width and exponential speed-up. — SIAM Journal on Computing. — 2006. — Т. 36. — С. 281. — DOI:
- Fedor V. Fomin, Frédéric Mazoit, Ioan Todinca. Computing branchwidth via efficient triangulations and blocks // Discrete Applied Mathematics. — 2009. — Т. 157, вип. 12. — С. 2726—2736. — DOI:. Архівовано з джерела 5 червня 2022. Процитовано 5 червня 2022..
- Jim Geelen, Bert Gerards, Neil Robertson[en], Geoff Whittle. On the excluded minors for the matroids of branch-width k // Journal of Combinatorial Theory, Series B. — 2003. — Т. 88, вип. 2. — С. 261—265. — DOI:.
- Jim Geelen, Bert Gerards, Geoff Whittle. Branch-width and well-quasi-ordering in matroids and graphs // Journal of Combinatorial Theory, Series B. — 2002. — Т. 84, вип. 2. — С. 270—290. — DOI:.
- Jim Geelen, Bert Gerards, Geoff Whittle. Proc. International Congress of Mathematicians. — 2006. — Т. III. — С. 827–842. Архівовано з джерела 11 серпня 2017
- Jim Geelen, Bert Gerards, Geoff Whittle. Excluding a planar graph from GF(q)-representable matroids // Journal of Combinatorial Theory, Series B. — 2007. — Т. 97, вип. 6. — С. 971—998. — DOI:..
- Qian-Ping Gu, Hisao Tamaki. Optimal branch-decomposition of planar graphs in O(n3) time // ACM Transactions on Algorithms. — 2008. — Т. 4, вип. 3. — С. 30:1—30:13. — DOI:.
- Rhiannon Hall, James Oxley, Charles Semple, Geoff Whittle. On matroids of branch-width three // Journal of Combinatorial Theory, Series B. — 2002. — Т. 86, вип. 1. — С. 148—171. — DOI:.
- Illya V. Hicks. Branch Decompositions and their Applications. — Rice University, 2000. — (Ph.D. thesis) Архівовано з джерела 16 липня 2011
- Illya V. Hicks, Nolan B. McMurray, Jr. The branchwidth of graphs and their cycle matroids // Journal of Combinatorial Theory, Series B. — 2007. — Т. 97, вип. 5. — С. 681—692. — DOI:..
- Petr Hliněný. Proc. 28th International Symposium on Mathematical Foundations of Computer Science (MFCS '03). — Springer-Verlag, 2003. — Т. 2747. — С. 470–479. — (Lecture Notes in Computer Science) — DOI:
- Petr Hliněný, Geoff Whittle. Matroid tree-width // European Journal of Combinatorics. — 2006. — Т. 27, вип. 7. — С. 1117—1128. — DOI:. Архівовано з джерела 6 березня 2012. Процитовано 5 червня 2022.
- Додатки й виправлення: Petr Hliněný, Geoff Whittle. Addendum to matroid tree-width // European Journal of Combinatorics. — 2009. — Т. 30, вип. 4. — С. 1036—1044. — DOI:.
- Frédéric Mazoit, Stéphan Thomassé. Surveys in Combinatorics 2007 / Anthony Hilton, John Talbot. — Cambridge University Press, 2007. — Т. 346. — С. 275. — (London Mathematical Society Lecture Note Series) Архівовано з джерела 28 червня 2012
- Sang-il Oum, Paul Seymour. Testing branch-width // Journal of Combinatorial Theory. — 2007. — Т. 97, вип. 3. — С. 385—393. — (Series B). — DOI:.
- Neil Robertson [en], Paul D. Seymour. Graph minors. X. Obstructions to tree-decomposition // Journal of Combinatorial Theory. — 1991. — Т. 52, вип. 2. — С. 153—190. — DOI:.
- Paul D. Seymour. Call routing and the ratcatcher // Combinatorica. — 1994. — Т. 14, вип. 2. — С. 217—241. — DOI:.