Максимальное совпадение M с условием G [M] не содержит 2K_2

11

Есть ли в литературе что-нибудь близкое к следующей проблеме:

Дан двудольный граф G(V,E) со сбалансированным разделением на две части {U,W} существует ли идеальное соответствие M в G такой, что на каждые 2 ребра u1w1,u2w2Mесть преимущество u1w2 или край u2w1 (или оба) в G?

Другими словами, есть ли идеальное соответствие M такой, что индуцированный подграф G[M] является 2K2-бесплатно. (При сбалансированном разделении я имел в виду|U|=|W|.)

Дополнительное условие является чем-то вроде противоположной крайности тому, что используется в задаче индуцированного сопоставления. Еще одна, возможно, связанная с этим проблема - поиск соответствия максимального размераM в двудольном графе G такое, что сжатие ребер в M минимизирует количество ребер, оставшихся в графе.

Я проверил список соответствующих проблем, приведенных Пламмером в разделе «Сопоставление и упаковка вершин»: насколько они сложны? безуспешно.

PS: эта проблема является частным случаем решения этой проблемы: - для данного kNесть ли максимальное совпадение M двудольного графа G такой, что G[M] является 2K2и |M|>k, Если входной график является сбалансированным двудольным иk=|U|мы получаем вышеупомянутую проблему.

Спасибо.

Кириак Антоний
источник
идеальное совпадение не может быть правильным словом. Мы в основном спрашиваем, есть ли максимальное совпадение, имеющее размер|U|с упомянутой собственностью.
Cyriac Antony
В некотором смысле мы просим нечто противоположное тому, что называется сильным соответствием. Сильное соответствиеM на графике G это совпадение M такой, что нет края в G соединяя любые два края M
Кириак Антоний
Извините G[M]Я имел в виду подграф G индуцируется вершинами «в» M
Кириак Антоний

Ответы:

5

Сюрприз! (для меня).
Этот тип соответствия уже изучен в литературе. Они называются связанными совпадениями .

Они были представлены Пламмером, Штибитцем и Тофтом в их исследовании гипотезы Хадвигера. См. Главу «Связанные совпадения» Кэмерона в книге «Комбинаторная оптимизация - Эврика, вы сжимаетесь!»

Статус связанных совпадений в двудольных графах (необязательно сбалансированный) открыт, насколько мне известно ( я буду обновлять ). Взвешенная версия задачи является NP-полной для двудольных графов. Задача разрешима за полиномиальное время для хордальных двудольных графов.

Обновление: проблема является NP-полной для сбалансированных двудольных графов (то есть, точная проблема, заданная в вопросе). Это доказано в работе Alon et al. " Способность к многозадачности: результаты твердости и улучшенные конструкции ". Они также сообщают, что найти размер наибольшего связанного совпадения трудно приблизительно в пределахn1ϵ если NP = co-RP.

Примечания, добавленные ранее (сохранены для заинтересованных людей):
« Связанные соответствия в хордовых двудольных графах » Джобсона и соавт. (doi: https://doi.org/10.1016/j.disopt.2014.06.003 ) и « Связанные соответствия в специальных семействах графов » по Караджанису (тезис) - две заметные ссылки.

Кириак Антоний
источник
1

Есть еще один способ задать этот вопрос. Есть ли идеальное соответствиеM сбалансированного двудольного графа G так что каждая пара ребер в M точно на расстоянии 1 друг от друга в G?
(Расстояние между краямиe а также e длина кратчайшего пути из вершины e до вершины e).

Благодаря этому дополнительное условие сводится к нахождению подмножества вершин из линейного графа. L(G) из Gкоторые находятся попарно на расстоянии ровно 2. Таким образом, проблема нахождения множества вершин максимального размера на расстоянии ровно 2 друг от друга является потенциальной проблемой (быть близкой к рассматриваемой проблеме). В недавней работе « Об алгоритмических аспектах сильного подкрашивания» (М.А. Шалу, С. Виджаякумар, С. Деви Ямини и Т.П. Сандхья) они называют эту проблему сильным множеством.

Известно, что проблема множества Stong является NP-полной в некоторых классах графов. Я не знаю его статус на линейных графиках двудольных графиков. В документе говорится, что он является NP-полным на двудольных графах. Наш интерес здесь будет в классе линейных графов двудольных графов.

Кириак Антоний
источник
отредактировано для исправления ошибки; Я думал, что линейные графики двудольных графов являются двудольными. :)
Cyriac Antony
Я думаю, что в вашем определении расстояния между ребрами должно быть +1 (по текущему определению ребра M будут на расстоянии 1, так как существует ребро - путь длиной 1 -, соединяющий каждую пару ребер М, но вы на самом деле имеете в виду расстояние 2).
Флоран Фуко
исправил это как "края ... находятся на расстоянии 1 друг от друга". Спасибо @Florent Фуко
Cyriac Antony
Это работает, но теперь, к сожалению, ваше «расстояние ребер» не соответствует расстоянию между вершинами соответствующих вершин линейного графа.
Флоран Фуко
1
Чтобы приблизить моделирование к вашей проблеме, напомним, что максимальное соответствие в графе соответствует максимальному независимому набору в его линейном графике. Таким образом, в линейном графике вы ищете сильный набор, который также является максимально независимым набором (в частности, он также должен быть доминирующим набором).
Флоран Фуко