Дан двудольный граф, состоящий из L и R долей. Требуется выбрать минимальное количество вершин из R, так, чтобы для каждой вершины из L было хотя бы одно ребро, соединяющее её с какой-то выбранной вершиной из R.
Задача слегка напоминает минимальное вершинное покрытие, только тут можно выбирать вершины только из 1-й доли.
Если вам можно брать вершины только из одной доли, то это задача set cover (покрытие множества). Каждая вершина в R задает множество в L и вам надо взять минимальное их количество, чтобы все L было покрыто. Это NP-сложная задача и у нее есть только медленные решения, вроде перебора. Еще можно свести ее к задаче целочисленного линейного программирования и решать каким-нибудь солвером.
Спасибо. А если вместо ЛП перевести её в SAT, зафиксировав min количество вершин = k и бинарным поиском найти k, только там помимо клозов, относящихся к самой проблеме ещё будет C(k, n) клозов типа что выбрано ровно k каких-то вершин и не выбраны остальные, наверное это проблемно будет перевести в SAT
