Есть ли в литературе что-нибудь близкое к следующей проблеме:
Дан двудольный граф со сбалансированным разделением на две части существует ли идеальное соответствие в такой, что на каждые 2 ребра есть преимущество или край (или оба) в ?
Другими словами, есть ли идеальное соответствие такой, что индуцированный подграф является -бесплатно. (При сбалансированном разделении я имел в виду.)
Дополнительное условие является чем-то вроде противоположной крайности тому, что используется в задаче индуцированного сопоставления. Еще одна, возможно, связанная с этим проблема - поиск соответствия максимального размера в двудольном графе такое, что сжатие ребер в минимизирует количество ребер, оставшихся в графе.
Я проверил список соответствующих проблем, приведенных Пламмером в разделе «Сопоставление и упаковка вершин»: насколько они сложны? безуспешно.
PS: эта проблема является частным случаем решения этой проблемы: - для данного есть ли максимальное совпадение двудольного графа такой, что является и , Если входной график является сбалансированным двудольным имы получаем вышеупомянутую проблему.
Спасибо.
Ответы:
Сюрприз! (для меня).
Этот тип соответствия уже изучен в литературе. Они называются связанными совпадениями .
Они были представлены Пламмером, Штибитцем и Тофтом в их исследовании гипотезы Хадвигера. См. Главу «Связанные совпадения» Кэмерона в книге «Комбинаторная оптимизация - Эврика, вы сжимаетесь!»
Статус связанных совпадений в двудольных графах (необязательно сбалансированный) открыт, насколько мне известно ( я буду обновлять ). Взвешенная версия задачи является NP-полной для двудольных графов. Задача разрешима за полиномиальное время для хордальных двудольных графов.
Обновление: проблема является NP-полной для сбалансированных двудольных графов (то есть, точная проблема, заданная в вопросе). Это доказано в работе Alon et al. " Способность к многозадачности: результаты твердости и улучшенные конструкции ". Они также сообщают, что найти размер наибольшего связанного совпадения трудно приблизительно в пределахn1−ϵ если NP = co-RP.
Примечания, добавленные ранее (сохранены для заинтересованных людей):
« Связанные соответствия в хордовых двудольных графах » Джобсона и соавт. (doi: https://doi.org/10.1016/j.disopt.2014.06.003 ) и « Связанные соответствия в специальных семействах графов » по Караджанису (тезис) - две заметные ссылки.
источник
Есть еще один способ задать этот вопрос. Есть ли идеальное соответствиеM сбалансированного двудольного графа G так что каждая пара ребер в M точно на расстоянии 1 друг от друга в G ? e а также e′ длина кратчайшего пути из вершины e до вершины e′ ).
(Расстояние между краями
Благодаря этому дополнительное условие сводится к нахождению подмножества вершин из линейного графа.L(G) из G которые находятся попарно на расстоянии ровно 2. Таким образом, проблема нахождения множества вершин максимального размера на расстоянии ровно 2 друг от друга является потенциальной проблемой (быть близкой к рассматриваемой проблеме). В недавней работе « Об алгоритмических аспектах сильного подкрашивания» (М.А. Шалу, С. Виджаякумар, С. Деви Ямини и Т.П. Сандхья) они называют эту проблему сильным множеством.
Известно, что проблема множества Stong является NP-полной в некоторых классах графов. Я не знаю его статус на линейных графиках двудольных графиков. В документе говорится, что он является NP-полным на двудольных графах. Наш интерес здесь будет в классе линейных графов двудольных графов.
источник