Индуцированный путь

Индуцированный путь длины четыре в кубе . Поиск самого длинного индуцированного пути в гиперкубе известен как задача «змея в ящике» .

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

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

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

Пример

Максимальные длины змей ( L _s ) и витков ( L _c ) в задаче «змеи в коробке» для размерностей n от 1 до 4

На иллюстрации изображен куб, граф с восемью вершинами и двенадцатью ребрами, а также индуцированный путь длиной четыре в этом графе. Простой анализ случая показывает, что в кубе больше не может быть индуцированного пути, хотя у него есть индуцированный цикл длиной шесть. Проблема нахождения самого длинного индуцированного пути или цикла в гиперкубе, впервые поставленная Каутцем (1958) , известна как проблема «змеи в ящике» и широко изучалась благодаря ее приложениям в теории кодирования и инженерии. .

Характеристика семейств графов

Многие важные семейства графов можно охарактеризовать с точки зрения индуцированных путей или циклов графов в семействе.

• Тривиально, связные графы без индуцированного пути длины два являются полными графами , а связные графы без индуцированного цикла являются деревьями .
• Граф без треугольников — это граф без индуцированного цикла длины три.
• Кографы — это в точности графы без индуцированных путей длины три.
• Хордальные графы — это графы, в которых нет индуцированного цикла длиной четыре и более.
• Графы без четных дырок — это графы, не содержащие индуцированных циклов с четным числом вершин.
• Тривиально совершенные графы — это графы, в которых нет ни индуцированного пути длины три, ни индуцированного цикла длины четыре.
• По сильной теореме о совершенных графах идеальные графы — это графы без нечетных дырок и нечетных антидырок.
• Дистанционно -наследственные графы — это графы, в которых каждый индуцированный путь является кратчайшим, и графы, в которых каждые два индуцированных пути между одними и теми же двумя вершинами имеют одинаковую длину.
• Блочные графы — это графы, в которых существует не более одного индуцированного пути между любыми двумя вершинами, а связные блочные графы — это графы, в которых существует ровно один индуцированный путь между любыми двумя вершинами.

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

NP-полно определить Для графа G и параметра k , имеет ли граф индуцированный путь длиной не менее k . Гари и Джонсон (1979) приписывают этот результат неопубликованному сообщению Михалиса Яннакакиса . Однако эта проблема может быть решена за полиномиальное время для определенных семейств графов, таких как графы без тройных астероидов. или графики без длинных дыр.

Также NP-полно определить, можно ли разделить вершины графа на два индуцированных пути или два индуцированных цикла. Как следствие, определение индуцированного номера пути графа является NP-трудным.

Сложность аппроксимации задач о самом длинном индуцированном пути или цикле может быть связана со сложностью поиска больших независимых множеств в графах посредством следующего сокращения. Из любого графа G с n вершинами сформируйте другой граф H с вдвое большим количеством вершин, чем G , добавив к G n ( n − 1)/2 вершины, имеющие по два соседа каждая, по одной на каждую пару вершин в G . Тогда, если G имеет независимое множество размера k , H должен иметь индуцированный путь и индуцированный цикл длины 2 k образованный чередованием вершин независимого множества в G с вершинами I. , И наоборот, если H имеет индуцированный путь или цикл длины k , любой максимальный набор несмежных вершин в G из этого пути или цикла образует независимое множество в G размера не менее k /3. Таким образом, размер максимального независимого множества в G находится в пределах постоянного множителя размера самого длинного индуцированного пути и самого длинного индуцированного цикла в H . Следовательно, согласно результатам Хостада (1996) о неаппроксимируемости независимых множеств, если только NP = ZPP, не существует алгоритма с полиномиальным временем для аппроксимации самого длинного индуцированного пути или самого длинного индуцированного цикла с точностью до коэффициента O( n ^1/2-е ) оптимального решения.

Дыры (и антидыры в графах без хордовых циклов длины 5) в графе с n вершинами и m ребрами могут быть обнаружены за время (n+m ² ).

Атомные циклы

Атомарные циклы — это обобщение безхордовых циклов, не содержащих n -хорд. Для некоторого цикла n -хорда определяется как путь длины n, соединяющий две точки цикла, где n меньше длины кратчайшего пути в цикле, соединяющего эти точки. Если цикл не имеет n -хорд, он называется атомарным циклом, поскольку его нельзя разложить на более мелкие циклы. В худшем случае атомные циклы в графе можно пронумеровать за O( m ² ) время, где m — количество ребер в графе.

Ссылки

• Бариоли, Франческо; Фаллат, Шон; Хогбен, Лесли (2004). «Вычисление минимального ранга и числа покрытий путей для определенных графов» (PDF) . Линейная алгебра и ее приложения . 392 : 289–303. дои : 10.1016/j.laa.2004.06.019 .
• Берман, Петр; Шнитгер, Георг (1992). «О сложности аппроксимации задачи о независимом множестве» . Информация и вычисления . 96 (1): 77–94. дои : 10.1016/0890-5401(92)90056-L .
• Бакли, Фред; Харари, Фрэнк (1988). «О самых длинных индуцированных путях в графах». Китайский ежеквартальный математический журнал . 3 (3): 61–65.
• Шартран, Гэри ; Макканна, Джозеф; Шервани, Навид; Хоссейн, Моаззем; Хашми, Джахангир (1994). «Индуцированное число путей двудольных графов». Арс Комбинатория . 37 : 191–208.
• Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман . п. 196 .
• Гашлер, Майкл; Мартинес, Тони (2012). «Надежное многообразное обучение с помощью CycleCut» (PDF) . Наука о связях . 24 (1): 57–69. дои : 10.1080/09540091.2012.664122 .
• Гаврил, Фаника (2002). «Алгоритмы для путей, индуцированных максимальным весом». Письма об обработке информации . 81 (4): 203–208. дои : 10.1016/S0020-0190(01)00222-8 .
• Хостад, Йохан (1996). «Клик трудно аппроксимировать в пределах n ^1-е SFCS.1996.548522 Труды 37-го ежегодного симпозиума IEEE по основам информатики . Стр. 627–636. doi : 10.1109/ .
• Каутц, Уильям Х. (июнь 1958 г.). «Коды проверки ошибок на единичном расстоянии». IRE-транзакции на электронных компьютерах . ИС-7 (2): 179–180. дои : 10.1109/TEC.1958.5222529 . S2CID   26649532 .
• Крач, Дитер; Мюллер, Хайко; Тодинка, Иоанн (2003). «Набор вершин обратной связи и самый длинный индуцированный путь на графах без AT» . Теоретико-графовые концепции в информатике . Берлин: Конспекты лекций по информатике, Vol. 2880, Шпрингер-Верлаг. стр. 309–321. дои : 10.1007/b93953 . Архивировано из оригинала 25 ноября 2006 г.
• Ле, Хоанг-Оан; Ле, Ван Банг; Мюллер, Хайко (2003). «Разбиение графа на непересекающиеся индуцированные пути или циклы» (PDF) . Дискретная прикладная математика . Второй международный коллоквиум «Journées de l'Informatique Messine», Мец, 2000. 131 (1): 199–212. дои : 10.1016/S0166-218X(02)00425-0 . Архивировано из оригинала (PDF) 03 марта 2016 г.
• Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012). «Глава 6. Деревья ограниченной высоты и глубина дерева». Разреженность: графы, структуры и алгоритмы . Алгоритмы и комбинаторика. Том. 28. Гейдельберг: Шпрингер. стр. 115–144. дои : 10.1007/978-3-642-27875-4 . ISBN  978-3-642-27874-7 . МР   2920058 .
• Николопулос, Ставрос Д.; Палиос, Леонидас (2004). «Обнаружение дырок и антидырок в графах» . Материалы 15-го симпозиума ACM-SIAM по дискретным алгоритмам . стр. 850–859.