Есть ли у этой задачи название?

Question

[floppa322]

Дан двудольный граф, состоящий из L и R долей. Требуется выбрать минимальное количество вершин из R, так, чтобы для каждой вершины из L было хотя бы одно ребро, соединяющее её с какой-то выбранной вершиной из R.

Задача слегка напоминает минимальное вершинное покрытие, только тут можно выбирать вершины только из 1-й доли.

Answer 1

[Wataru]

Если вам можно брать вершины только из одной доли, то это задача set cover (покрытие множества). Каждая вершина в R задает множество в L и вам надо взять минимальное их количество, чтобы все L было покрыто. Это NP-сложная задача и у нее есть только медленные решения, вроде перебора. Еще можно свести ее к задаче целочисленного линейного программирования и решать каким-нибудь солвером.

Comments

[floppa322]

Спасибо. А если вместо ЛП перевести её в SAT, зафиксировав min количество вершин = k и бинарным поиском найти k, только там помимо клозов, относящихся к самой проблеме ещё будет C(k, n) клозов типа что выбрано ровно k каких-то вершин и не выбраны остальные, наверное это проблемно будет перевести в SAT

[Wataru]

floppa322, Да, скорее всего. ЛП будет эффективнее. SAT у вас будет экспоненциальное количество условий.