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