Здравствуйте, SergASh, Вы писали:

SAS>Привет всем!

SAS>Есть ненаправленный граф. Требуется разбить множество его вершин на две части A и B так, чтобы вершины из B соединялись только с вершинами из A, но не между собой. Из всех таких разбиений нужно выбрать то, при котом во множество A попадает наименьшее количество вершин.

SAS>Какие будут соображения?

Прошлым летом я делал что-то аналогичное для орграфа:
https://sites.google.com/site/alex0shkotin/grafy/wikipedia-category-graph
может пригодится