Релаксация известной $NP$-полной задачи распознавания свойства полярности произвольного графа, приводящая к быстрому полиномиальному алгоритму

Рассматривается класс полярных графов и некоторые его подклассы. Граф $G$ называется полярным, если существует такое разбиение $VG=A\cup B$ его множества вершин, что все связные компоненты порожденного подграфа $G(B)$ и дополнительного $\overline{G(A)}$ — полные графы.
Известно, что задача распознавания полярности произвольного графа является $NP$-полной. Предложена релаксация вышеупомянутой задачи, приводящая к быстрому полиномиальному алгоритму.