Установить покрытие (удар) на бикубических (т.е. двудольных 3-регулярных) графиках
Я пытался придумать эффективный алгоритм для решения этой проблемы. Дело в том, что я знаю, что проблема попадания в двудольных графах является NP-трудной, и то же самое относится к кубическим графам. Тем не менее, я не совсем уверен, существует ли полиномиальное решение, если входной граф на самом деле является двудольным и 3-регулярным.
У меня есть двудольный граф с частями X и Y. Каждый узел в X имеет 3 соседей, и каждый узел в X имеет связанную стоимость. Я хочу найти подмножество A из X с минимальной общей стоимостью (то есть суммой затрат для узлов в A) таким образом, чтобы они "поражали" каждый узел в Y (то есть каждый узел в Y смежен с некоторыми узел в а).
В частности, это очень легко перевести на LP-задачу, но матрица не совсем унимодулярна. Кроме того, учитывая, что граф имеет такую большую структуру, кажется разумным, что жадный подход может работать. Если у кого-то есть идея, это было бы здорово.
Благодарю.