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