Вынужденное соответствие - Induced matching
В теория графов, индуцированное соответствие или же сильное соответствие является подмножеством ребер неориентированный граф не имеют общих вершин (это соответствие ) и включает каждое ребро, соединяющее любые две вершины в подмножестве (это индуцированный подграф ).
Индуцированное согласование также можно описать как независимый набор в квадрат из линейный график данного графа.[1]
Сильная окраска и окрестности
Минимальное количество индуцированных паросочетаний, на которые можно разбить ребра графа, называется его сильный хроматический индекс, по аналогии с хроматический индекс графа - минимальное количество паросочетаний, на которые можно разбить его ребра.[2] Это равно хроматическое число квадрата линейного графика. Теорема Брукса, примененный к квадрату линейного графа, показывает, что сильный хроматический индекс не более чем квадратичен в максимальной степени данного графа, но лучшие постоянные множители в квадратичной оценке могут быть получены другими методами.[3]
В Проблема Ружи – Семереди касается плотности ребер сбалансированных двудольных графов с линейным сильным хроматическим индексом. В равной степени это касается плотности другого класса графов, локально линейные графы в которой район каждой вершины является индуцированным паросочетанием.[4] Ни один из этих типов графов не может иметь квадратичного числа ребер, но конструкции известны для графов этого типа с почти квадратичным числом ребер.[5]
Вычислительная сложность
Нахождение индуцированного соответствия размера не менее является НП-полный (и, таким образом, нахождение индуцированного соответствия максимального размера является NP-жесткий ). Ее можно решить за полиномиальное время за хордовые графы, поскольку квадраты линейных графов хордовых графов идеальные графики.[6]Более того, ее можно решить за линейное время за хордовые графы [7].Если не произошел неожиданный обвал в полиномиальная иерархия происходит, то наибольшее индуцированное согласование нельзя аппроксимировать с точностью до коэффициент аппроксимации за полиномиальное время.[8]
Проблема также в W [1] -жесткий, что означает, что даже обнаружение небольшого индуцированного соответствия заданного размера вряд ли будет алгоритм значительно быстрее, чем поиск грубой силы подход попробовать все -наборы ребер.[9] Однако проблема поиска вершины, удаление которых оставляет индуцированное сопоставление, есть управляемый с фиксированными параметрами.[10] Проблема также может быть решена точно на -вершинные графики во времени с экспоненциальным пространством или во времени с полиномиальное пространство.[11]
Смотрите также
Рекомендации
- ^ Кэмерон, Кэти (2004), "Индуцированные сопоставления в графах пересечений", Дискретная математика, 278 (1–3): 1–9, Дои:10.1016 / j.disc.2003.05.001, МИСТЕР 2035386
- ^ Fouquet, J.-L .; Жоливе, Ж.-Л. (1983), "Сильная раскраска ребер графов и приложения к мульти-k-угольники ", Ars Combinatoria, 16 (А): 141–150, МИСТЕР 0737086
- ^ Моллой, Майкл; Рид, Брюс (1997), "Оценка сильного хроматического индекса графа", Журнал комбинаторной теории, Серия B, 69 (2): 103–109, Дои:10.1006 / jctb.1997.1724, HDL:1807/9474, МИСТЕР 1438613
- ^ Фрончек, Далибор (1989), «Локально линейные графы», Mathematica Slovaca, 39 (1): 3–6, HDL:10338.dmlcz / 136481, МИСТЕР 1016323
- ^ Ружа, И.З.; Семереди, Э. (1978), «Тройные системы без шести точек, несущие три треугольника», Комбинаторика (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Коллок. Математика. Soc. Янош Бойяи, 18, Амстердам и Нью-Йорк: Северная Голландия, стр. 939–945, МИСТЕР 0519318
- ^ Кэмерон, Кэти (2008), "Максимальные индуцированные сопоставления для хордовых графов в линейном времени", специальный выпуск для Первой Монреальской конференции по комбинаторике и информатике, 1987, Алгоритмика, 52: 440–447, Дои:10.1016 / 0166-218X (92) 90275-F, МИСТЕР 1011265
- ^ Брандштадт, Андреас; Хоанг, Чин (1989), «Вынужденные сопоставления», Дискретная прикладная математика, 24 (1–3): 97–102, Дои:10.1007 / s00453-007-9045-2
- ^ Чалермсук, Париня; Лаэханукит, Бундит; Nanongkai, Danupon (2012), «Пересмотр графических продуктов: жесткость точного приближения индуцированного согласования, размерность точек и многое другое», Материалы двадцать четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, Филадельфия, Пенсильвания: SIAM, стр. 1557–1576, МИСТЕР 3202998
- ^ Мозер, Ханнес; Сикдар, Сомнатх (2009), "Параметризованная сложность индуцированной проблемы согласования", Дискретная прикладная математика, 157 (4): 715–727, Дои:10.1016 / j.dam.2008.07.011, МИСТЕР 2499485
- ^ Сяо, Минюй; Коу, Шаовей (2016), «Почти индуцированное сопоставление: линейные ядра и параметризованные алгоритмы», в Хеггернес, Пинар (ред.), Теоретико-графические концепции в компьютерных науках: 42-й международный семинар, WG 2016, Стамбул, Турция, 22–24 июня 2016 г., пересмотренные избранные статьи, Конспект лекций по информатике, 9941, Берлин: Springer, стр. 220–232, Дои:10.1007/978-3-662-53536-3_19, МИСТЕР 3593958
- ^ Сяо, Минюй; Тан, Хуан (2017), «Точные алгоритмы для максимального индуцированного сопоставления», Информация и вычисления, 256: 196–211, Дои:10.1016 / j.ic.2017.07.006, МИСТЕР 3705425