Abstract:
Considered the class of polar graphs and some of its subclasses. Graph $G=(V,E)$ is called polar if there
exist a partition $VG=A\cup B$ of its vertex set such that all connected components of subgraphs $G(B)$ and
$\overline{G(A)}$ are cliques.
It is known that the polar graph recognition problem is $NP$-complete.
In this paper the relaxation of the mentioned problem leading to the fast polynomial-time algorithm is
proposed.