Сложность поиска графового разделителя с заданным свойством

Есть ли какие-либо известные результаты о сложности поиска разделителя (любого размера), удовлетворяющего заданному свойству?

Я знаю, что разделитель кликов легко найти (за полиномиальное время), а также знаю, что во многих работах рассматривается проблема поиска небольших разделителей или разделителей, которые оставляют связанные компоненты размера не более чем на долю размера исходного графа. Но что, если нужен сепаратор с другими свойствами, скажем, кубический, двудольный или двухсвязный? Также легко создавать свойства, которые трудно определить NP, поэтому было бы интересно различить случаи P и NPC.

Изменить: кто-то (который не является пользователем этого веб-сайта) только что сказал мне, что проблема является полиномиальной, если свойство «имеет универсальную вершину», и NP-полным, если свойство «индуцирует независимый набор» или «индуцирует полное двудольный граф ".

Наша статья:

http://arxiv.org/abs/1110.4765

показывает, что многие из этих проблем являются трактуемыми с фиксированными параметрами, т. е. мы можем решить за время f (k) * O (n + m), существует ли st-разделитель размера k. Это верно, например, для задачи поиска связанного st-разделителя, или разделителя, который является независимым множеством, или разделителя, который индуцирует двудольный граф. В следующей статье рассматривается проблема поиска 2-связного st-разделителя.

Также трудно определить, имеет ли граф разрез, который индуцирует несвязный граф , или граф с ровно k компонентами для всех k> = 2 . С другой стороны, связное разрезание легко (то есть k = 1).