Ветвевая декомпозиция

Ветвевое разложение сеточного графа , показывающее е-разделение. Разделение, декомпозиция и граф имеют ширину три.

В теории графов ветвящаяся декомпозиция неориентированного графа G представляет собой иерархическую кластеризацию ребер G , представленную некорневым бинарным деревом T с ребрами G в качестве листьев. Удаление любого ребра из T разбивает ребра G на два подграфа, а ширина разложения равна максимальному количеству общих вершин любой пары подграфов, сформированных таким образом. Ширина ветвления G G. это минимальная ширина любого ветвящегося разложения —

Ширина ветвей тесно связана с шириной дерева : для всех графов оба этих числа находятся в пределах постоянного коэффициента друг друга, и обе величины могут характеризоваться запрещенными минорами . Как и в случае с шириной дерева, многие проблемы оптимизации графов могут быть эффективно решены для графов с небольшой шириной ветвей. Однако, в отличие от ширины дерева, ширина ветвей планарных графов может быть вычислена точно за полиномиальное время . Декомпозиция ветвей и ширина ветвей также могут быть обобщены с графов на матроиды .

Определения

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

Ширина e-разделения — это количество вершин графа G , инцидентных как ребру E1 _, ребру E2 _{так и} ; то есть это количество вершин, которые являются общими для двух подграфов G ₁ и G ₂ . Ширина ветвевого разложения — это максимальная ширина любого из его e-разделений. Ширина ветвления G это минимальная ширина разложения ветвей G. —

Отношение к ширине дерева

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

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

Ширина резьбы

Основная статья: Ширина резьбы

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

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

Алгоритмы и сложность

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

Для плоских графов ширина ветвления может быть вычислена точно за полиномиальное время. В отличие от древовидной ширины, для которой сложность плоских графов является хорошо известной открытой проблемой. Оригинальный алгоритм определения планарной ширины ветвей, разработанный Полом Сеймуром и Робином Томасом , требовал времени O( n ² ) на графах с n вершинами, а их алгоритм построения ветвящегося разложения такой ширины занимал время O( n ⁴ ). Позже это было ускорено до O( n ³ ).

Как и в случае с шириной дерева, ширина ветвей может использоваться в качестве основы алгоритмов динамического программирования для многих NP-сложных задач оптимизации, используя количество времени, которое экспоненциально зависит от ширины входного графа или матроида. Например, Кук и Сеймур (2003) применяют динамическое программирование на основе ширины ветвей к задаче объединения нескольких частичных решений задачи коммивояжера в одно глобальное решение путем формирования разреженного графа из объединения частичных решений с использованием спектрального эвристика кластеризации , чтобы найти хорошую декомпозицию ветвей этого графа, и применение динамического программирования к декомпозиции. Фомин и Тиликос (2006) утверждают, что ширина ветвления работает лучше, чем ширина дерева при разработке алгоритмов с фиксированными параметрами на плоских графах по нескольким причинам: ширина ветвления может быть более жестко ограничена функцией интересующего параметра, чем границы ширины дерева. , его можно вычислить точно за полиномиальное время, а не просто аппроксимировать, и алгоритм его вычисления не имеет больших скрытых констант.

Обобщение на матроиды

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

Ширина ветвей является важным компонентом попыток распространить теорию миноров графа на миноры матроидов : хотя ширину дерева также можно обобщить на матроиды, и играет большую роль, чем ширина ветвления в теории миноров графа, ширина ветвления имеет более удобные свойства в условиях матроида. Робертсон и Сеймур предположили, что матроиды, представимые над любым конкретным конечным полем, , хорошо квазиупорядочены аналогично теореме Робертсона-Сеймура для графов, но до сих пор это было доказано только для матроидов ограниченной ширины ветвей. Кроме того, если минорно-замкнутое семейство матроидов, представимое в конечном поле, не включает графические матроиды всех планарных графов, то существует постоянная граница ширины ветвей матроидов в семействе, обобщающая аналогичные результаты для минорно-замкнутого графа. семьи.

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

Запрещенные несовершеннолетние

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

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

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

Ссылки

• Бодлендер, Ханс Л .; Тиликос, Димитриос М. (1997), "Конструктивные алгоритмы с линейным временем для определения ширины ветвей", Proc. 24-й Международный коллоквиум по автоматам, языкам и программированию (ICALP '97) , Конспекты лекций по информатике, том. 1256, Springer-Verlag, стр. 627–637, doi : 10.1007/3-540-63165-8_217 , hdl : 2117/96447 .
• Бодлендер, Ханс Л .; Тиликос, Димитриос М. (1999), «Графы с шириной ветвей не более трех», Journal of Algorithms , 32 (2): 167–194, doi : 10.1006/jagm.1999.1011 .
• Кук, Уильям; Сеймур, Пол Д. (2003), «Слияние туров посредством декомпозиции ветвей» (PDF) , INFORMS Journal on Computing , 15 (3): 233–248, doi : 10.1287/ijoc.15.3.233.16078 .
• Фомин Федор Владимирович; Тиликос, Димитриос М. (2006), «Доминирующие множества в плоских графах: ширина ветвей и экспоненциальное ускорение», SIAM Journal on Computing , 36 (2): 281, doi : 10.1137/S0097539702419649 .
• Фомин Федор Владимирович; Мазуа, Фредерик; Тодинка, Иоан (2009), «Вычисление ширины ветвей с помощью эффективных триангуляций и блоков» , Discrete Applied Mathematics , 157 (12): 2726–2736, doi : 10.1016/j.dam.2008.08.009 .
• Гилен, Джим ; Джерардс, Берт; Робертсон, Нил ; Уиттл, Джефф (2003), «Об исключенных минорах для матроидов с шириной ветвей k », Journal of Combinatorial Theory, Series B , 88 (2): 261–265, doi : 10.1016/S0095-8956(02)00046 -1 .
• Гилен, Джим ; Джерардс, Берт; Уиттл, Джефф (2002), «Ширина ветвей и хороший квазиупорядочение в матроидах и графах», Journal of Combinatorial Theory, Series B , 84 (2): 270–290, doi : 10.1006/jctb.2001.2082 .
• Гилен, Джим ; Джерардс, Берт; Уиттл, Джефф (2006), «К теории структуры матриц и матроидов» (PDF) , Proc. Международный конгресс математиков , вып. III, стр. 827–842 .
• Гилен, Джим ; Джерардс, Берт; Уиттл, Джефф (2007), «Исключение плоского графа из GF( q )-представимых матроидов» (PDF) , Journal of Combinatorial Theory, Series B , 97 (6): 971–998, doi : 10.1016/j.jctb. 2007.02.005 , заархивировано из оригинала (PDF) 24 сентября 2010 г.
• Гу, Цянь-Пин; Тамаки, Хисао (июль 2008 г.), «Оптимальное разложение ветвей планарных графов в O( n ³ ) время», Транзакции ACM по алгоритмам , 4 (3): 30:1–30:13, doi : 10.1145/1367064.1367070 .
• Холл, Рианнон; Оксли, Джеймс ; Семпл, Чарльз; Уиттл, Джефф (2002), «О матроидах с шириной ветки три», Журнал комбинаторной теории, серия B , 86 (1): 148–171, doi : 10.1006/jctb.2002.2120 .
• Хикс, Илья В. (2000), Ветвевые разложения и их приложения , доктор философии. диссертация, Университет Райса, заархивировано из оригинала 16 июля 2011 г. , получено 6 июля 2010 г.
• Хикс, Илья В.; МакМюррей, Нолан Б. младший (2007), «Ширина ветвей графов и их цикловых матроидов», Журнал комбинаторной теории, серия B , 97 (5): 681–692, doi : 10.1016/j.jctb.2006.12.007 .
• Хлинены, Петр (2003), «О свойствах матроида, определяемых в логике MSO», Proc. 28-й Международный симпозиум по математическим основам информатики (MFCS '03) , Конспекты лекций по информатике, том. 2747, Springer-Verlag, стр. 470–479, номер документа : 10.1007/978-3-540-45138-9\_41.
• Хлиненый, Петр; Уиттл, Джефф (2006), «Ширина дерева матроидов» (PDF) , European Journal of Combinatorics , 27 (7): 1117–1128, doi : 10.1016/j.ejc.2006.06.005 , заархивировано из оригинала (PDF) 06 марта 2012 г. , получено 6 июля 2010 г.
  • Добавлю и исправлю: Хлиненый, Петр; Уиттл, Джефф (2009), «Дополнение к ширине дерева матроидов», European Journal of Combinatorics , 30 (4): 1036–1044, doi : 10.1016/j.ejc.2008.09.028 .
• Мазуа, Фредерик; Томассе, Стефан (2007), «Ширина графических матроидов», в Хилтоне, Энтони; Талбот, Джон (ред.), Обзоры по комбинаторике, 2007 г. (PDF) , Серия лекций Лондонского математического общества, том. 346, Издательство Кембриджского университета, с. 275 .
• Oum, Санг-ил ; Сеймур, Пол (2007), «Тестирование ширины ветвей», Журнал комбинаторной теории , серия B, 97 (3): 385–393, doi : 10.1016/j.jctb.2006.06.006 , MR   2305892 .
• Робертсон, Нил ; Сеймур, Пол Д. (1991), «Минорные графы. X. Препятствия к разложению дерева», Journal of Combinatorial Theory , 52 (2): 153–190, doi : 10.1016/0095-8956(91)90061-N .
• Сеймур, Пол Д .; Томас, Робин (1994), «Маршрутизация вызовов и крысолов», Combinatorica , 14 (2): 217–241, doi : 10.1007/BF01215352 .