Алгоритм приведения двудольного графа к двудольно-пороговому виду

Тройка $(x, v, y)$ различных вершин графа $G = (V, E)$ такая, что $xv\in E$ и $vy\notin E$, называется повышающей, если $\mathrm{deg}(x) \leq \mathrm{deg}(y)$, и понижающей, если $\mathrm{deg}(x) \geq 2 + \mathrm{deg}(y)$. Преобразование $\phi$ графа $G$ такое, что $\phi(G) = G - xv + vy$, называется вращением ребра в графе $G$ вокруг вершины $v$, отвечающим тройке $(x, v, y)$. Вращение ребра в графе $G$, отвечающее тройке $(x, v, y)$, называется повышающим, если тройка $(x, v, y)$ повышающая, и понижающим, если тройка $(x, v, y)$ понижающая. Вращение $\phi$ ребра в графе $G$ является повышающим тогда и только тогда, когда обратное к нему вращение ребра в графе $\phi(G)$ является понижающим. Двудольный граф $H = (V_1, E, V_2)$ будем называть двудольно-пороговым графом, если он не имеет повышающих троек таких, что $x, y \in V_1$, $v \in V_2$ или $x, y \in V_2$, $v \in V_1$. Вращение ребра, отвечающее тройке вершин $(x, v, y)$, такое, что $x, y \in V_1$ и $v \in V_2$ ($x, y \in V_2$ и $v \in V_1$), будем называть $V_1$-вращением ($V_2$-вращением) ребра. Любой двудольный граф $H = (V_1, E, V_2)$ можно преобразовать в двудольно-пороговый граф с помощью конечной последовательности $V_1$-вращений ($V_2$-вращений) ребер. Целью работы является построение полиномиального алгоритма, который преобразует любой двудольный граф $H = (V_1, E, V_2)$ в двудольно-пороговый граф с помощью кратчайшей последовательности, состоящей из $V_1$-вращений ребер.