На всего лишь нужно найти группу вершин, в которую обязательно входит та вершина из которой мы запустили бфс и она имеет максимальный размер. Я предложил способ выделения такого множества. Наверно, стоило оговорить что если две вершины принадлежат множеству 1 и соединены ребром, то одну из них стоит удалить. Я посчитал что это уже к тонкостям реализации относится.

Максимальный по включению или количеству вершин? Если второе, то это NP-полная задача. Если первое, то это, очевидно, неправильно.

Что неправильно, мне не очевидно. Условие, гласящее о том, что любые 2 вершины содержащиеся в первом множестве не должны иметь ребра не обязано выполняться для второго множества. Второе множество будет обработано в дальнейшем.

Ну рассмотрим граф со следующими ребрами: 1-2, 2-3, 3-4, 4-5, 5-2. В начале удалим вершины 1 и 4, поскольку они образуют максимальное по включению независимое множество. После этого останется цепочка из 3 вершин, которую можно покрыть двумя множествами. Итого, получили ответ 3. Но ведь граф можно покрыть и двумя множествами: {1, 3, 5} и {2, 4}.

1) В данном случае алгоритм найдет 2 множества. {1, 3, 5} и {2, 4}. Это не трудно увидеть, если нарисовать граф. Возможно, увидев код, Вы лучше поймете идею моего решения.

http://pastebin.com/dpNXHiuP

2) Меня действительно напрягает то, что решенная мною задача по сути является эквивалентной NP-полной, описанной выше, но работает за полиномиальное время.

Я прекрасно понимаю, какие вершины найдет алгоритм. Но он — не более, чем шаманство для поиска максимального по включению независимого множества. Просто не хотелось придумывать какой-то сложный граф, чтобы завалить именно такой способ выбора.

Еще с самого начала было ясно, что задача NP-полная и описанный алгоритм — попытка жадно найти приближенное решение. Я просто попытался указать на ошибку, но вижу что спорить бесполезно.

Наверное, все — таки Вы правы. Что то я очень сильно сомневаюсь в своих способностях придумать полиномиальное решение для NP — полной задачи.