Максимальное двустороннее сопоставление - это набор ребер в двудольном графе, причем два ребра не являются смежными.Максимальный независимый набор - это набор узлов (вершин) в графе, при этом две вершины не являются смежными.
Таким образом, вы можете преобразовать задачу двустороннего сопоставления в независимый набор, преобразовав каждое ребро в двудольном графе вузел, а затем добавить ребро между всеми этими вновь созданными узлами, которые имеют общую конечную точку в исходном графе.Тогда максимальное независимое множество в новом графе соответствует максимальному двустороннему соответствию в исходной задаче.