Индуцированное соответствие

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

Индуцированное паросочетание также можно описать как независимое множество в квадрате линейного графа данного графа. ^[1]

Яркая окраска и окрестности

Минимальное число индуцированных паросочетаний, на которые можно разбить ребра графа, называется его сильным хроматическим индексом , по аналогии с хроматическим индексом графа — минимальным числом паросочетаний, на которые можно разбить его ребра. ^[2] Оно равно хроматическому числу квадрата линейного графика. Теорема Брукса , примененная к квадрату линейного графика:показывает, что сильный хроматический индекс не более чем квадратичен в максимальной степени данного графа, но лучшие постоянные множители в квадратичной оценке можно получить другими методами. ^[3]

Проблема Ружи–Семереди касается плотности ребер сбалансированных двудольных графов с линейным сильным хроматическим индексом. Эквивалентно, это касается плотности другого класса графов, локально линейных графов , в которых окрестность каждой вершины является индуцированным паросочетанием. ^[4] Ни один из этих типов графов не может иметь квадратичного числа ребер, но известны конструкции графов этого типа с почти квадратичным числом ребер. ^[5]

Вычислительная сложность

Нахождение индуцированного паросочетания размером не менее $k$ является NP-полным (и, следовательно, найти индуцированное паросочетание максимального размера NP-трудно ). Ее можно решить за полиномиальное время в хордальных графах , поскольку квадраты линейных графов хордальных графов являются совершенными графами . ^[6]Более того, ее можно решить за линейное время в хордальных графах ^[7].Если не произойдет неожиданный коллапс в полиномиальной иерархии ,наибольшее индуцированное паросочетание не может быть аппроксимировано с точностью до любого $n^{1-\varepsilon }$ коэффициент аппроксимации за полиномиальное время. ^[8]

Проблема также является W[1]-трудной , что означает, что даже поиск небольшого индуцированного паросочетания заданного размера $k$ вряд ли будет иметь алгоритм, значительно более быстрый, чем метод перебора , заключающийся в переборе всех $k$ -кортежи ребер. ^[9] Однако проблема поиска $k$ вершины, удаление которых оставляет индуцированное сопоставление, являются управляемыми с фиксированными параметрами . ^[10] Проблему также можно решить именно на $n$ -вершинные графы во времени $O(1.3752^{n})$ с экспоненциальным пространством или во времени $O(1.4231^{n})$ с полиномиальным пространством . ^[11]

См. также

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

Ссылки

^ Кэмерон, Кэти (2004), «Индуцированные сопоставления в графах пересечений», Discrete Mathematics , 278 (1–3): 1–9, doi : 10.1016/j.disc.2003.05.001 , MR 2035386
^ Фуке, Ж.-Л.; Жоливе, Ж.-Л. (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 , МР 1438613
^ Фрончек, Далибор (1989), «Локально линейные графы», Mathematica Slovaca , 39 (1): 3–6, hdl : 10338.dmlcz/136481 , MR 1016323
^ Ружа, Издательство ; Семереди, Э. (1978), «Тройные системы без шести точек, несущих три треугольника», Комбинаторика (Труды пятого венгерского коллоквиума, Кестхей, 1976), Vol. II , Colloq. Математика. Сок. Янош Бояи, том. 18, Амстердам и Нью-Йорк: Северная Голландия, стр. 939–945, МР 0519318
^ Кэмерон, Кэти (2008), «Максимально индуцированные совпадения для хордальных графов в линейном времени», специальный выпуск Первой Монреальской конференции по комбинаторике и информатике, 1987, Algorithmica , 52 : 440–447, doi : 10.1016/0166-218X(92 )90275-Ф , МР 1011265
^ Брандштедт, Андреас; Хоанг, Чинь (1989), «Индуцированные сопоставления», Discrete Applied Mathematics , 24 (1–3): 97–102, doi : 10.1007/s00453-007-9045-2
^ Чалермсук, Паринья; Лаеханукит, Бундит; Нанонгкай, Данупон (2012), «Возврат к графовым продуктам: жесткость аппроксимации индуцированного сопоставления, размерность частичного набора и многое другое», Труды двадцать четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Филадельфия, Пенсильвания: SIAM, стр. 1557– 1576, МР 3202998
^ Мозер, Ханнес; Сикдар, Сомнатх (2009), «Параметризованная сложность индуцированной задачи сопоставления», Discrete Applied Mathematics , 157 (4): 715–727, doi : 10.1016/j.dam.2008.07.011 , MR 2499485
^ Сяо, Мингю; Коу, Шаовей (2016), «Почти индуцированное сопоставление: линейные ядра и параметризованные алгоритмы», в Хеггернесе, Пинаре (ред.), Теоретико-графовые концепции в информатике: 42-й международный семинар, WG 2016, Стамбул, Турция, 22 июня– 24, 2016, Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 9941, Берлин: Springer, стр. 220–232, doi : 10.1007/978-3-662-53536-3_19 , ISBN. 978-3-662-53535-6 , МР 3593958
^ Сяо, Мингю; Тан, Хуан (2017), «Точные алгоритмы максимального индуцированного сопоставления», Information and Computation , 256 : 196–211, doi : 10.1016/j.ic.2017.07.006 , MR 3705425

[cam04-1] Кэмерон, Кэти (2004), «Индуцированные сопоставления в графах пересечений», Discrete Mathematics , 278 (1–3): 1–9, doi : 10.1016/j.disc.2003.05.001 , MR 2035386

[fj-2] Фуке, Ж.-Л.; Жоливе, Ж.-Л. (1983), «Сильная рёберная раскраска графов и приложения к мульти $-k$ -угольникам», Ars Combinatoria , 16 (A): 141–150, MR 0737086

[mr-3] Моллой, Майкл; Рид, Брюс (1997), «Оценка сильного хроматического индекса графа», Журнал комбинаторной теории , серия B, 69 (2): 103–109, doi : 10.1006/jctb.1997.1724 , hdl : 1807/9474 , МР 1438613

[f-4] Фрончек, Далибор (1989), «Локально линейные графы», Mathematica Slovaca , 39 (1): 3–6, hdl : 10338.dmlcz/136481 , MR 1016323

[rs78-5] Ружа, Издательство ; Семереди, Э. (1978), «Тройные системы без шести точек, несущих три треугольника», Комбинаторика (Труды пятого венгерского коллоквиума, Кестхей, 1976), Vol. II , Colloq. Математика. Сок. Янош Бояи, том. 18, Амстердам и Нью-Йорк: Северная Голландия, стр. 939–945, МР 0519318

[cam89-6] Кэмерон, Кэти (2008), «Максимально индуцированные совпадения для хордальных графов в линейном времени», специальный выпуск Первой Монреальской конференции по комбинаторике и информатике, 1987, Algorithmica , 52 : 440–447, doi : 10.1016/0166-218X(92 )90275-Ф , МР 1011265

[brahoa08-7] Брандштедт, Андреас; Хоанг, Чинь (1989), «Индуцированные сопоставления», Discrete Applied Mathematics , 24 (1–3): 97–102, doi : 10.1007/s00453-007-9045-2

[cln-8] Чалермсук, Паринья; Лаеханукит, Бундит; Нанонгкай, Данупон (2012), «Возврат к графовым продуктам: жесткость аппроксимации индуцированного сопоставления, размерность частичного набора и многое другое», Труды двадцать четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Филадельфия, Пенсильвания: SIAM, стр. 1557– 1576, МР 3202998

[ms-9] Мозер, Ханнес; Сикдар, Сомнатх (2009), «Параметризованная сложность индуцированной задачи сопоставления», Discrete Applied Mathematics , 157 (4): 715–727, doi : 10.1016/j.dam.2008.07.011 , MR 2499485

[xk-10] Сяо, Мингю; Коу, Шаовей (2016), «Почти индуцированное сопоставление: линейные ядра и параметризованные алгоритмы», в Хеггернесе, Пинаре (ред.), Теоретико-графовые концепции в информатике: 42-й международный семинар, WG 2016, Стамбул, Турция, 22 июня– 24, 2016, Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 9941, Берлин: Springer, стр. 220–232, doi : 10.1007/978-3-662-53536-3_19 , ISBN. 978-3-662-53535-6 , МР 3593958

[xt-11] Сяо, Мингю; Тан, Хуан (2017), «Точные алгоритмы максимального индуцированного сопоставления», Information and Computation , 256 : 196–211, doi : 10.1016/j.ic.2017.07.006 , MR 3705425

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]