Добрый день!
Задан связный двудольный граф B c долями L и R, в котором вершин в левой доле строго меньше чем в правой |L|<|R|. Задано максимальное паросочетание графа, в котором участвуют все вершины из L и часть вершин из R, ребра, образующие заданное паросочетание назовем базовыми ребрами. Известно, что в графе можно построить максиамльное паросочетание (т.е. паросочетание мощности L) с участием любого подмножества из R мощности L. Задача: удалить из графа как можно больше ребер, кроме базовых так, чтобы в получившемся графе осталась возможность построить максимальное паросочетание с любым подмножеством из R. Привожу пример графа, у которого |L|=3, |R|=5. Извините, что ссылкой, почему-то не могу вставить изображение
https://ibb.co/C6PHyGhПодскажите, пожалуйста, как решить такую задачу? Буду рад любым идеям (о раскрасках графа, об увеличивающих путях, максимальном потоке/минимальном разрезе, случайном удалении ребер и т.п.) Может быть кто-то сможет подсказать, можно ли свести данную задачу к какой-то известной? В идеале мне бы хотелось решить эту задачу точно, но если это трудно или долго, можно рассмотреть приближенные решения
Понятно, что можно рассмотреть все возможные варианты: сначала выбрать множество всех подмножеств для ребер, доступных к удалению, затем все подмножества вершин правой доли нужной мощности, а затем пробовать строить совершенное паросочетание по выбранным вершинам из R. Но это очень долго и даже для такого маленького примера как я привел число вариантов, для которых нужно построить паросочетание составит 2^9*C_5^3 = 512*10 = 5120. Т.е. 5120 раз нужно будет запустить алгоритм поиска совершенного паросочетания, который работает за o(n^3). Это слишком долго, может быть есть другие варианты?
Спасибо!
