An algorithm for finding homogeneous pairs (Q674438)

\((Q_1,Q_2)\) is a homogeneous pair in an undirected finite graph \(G= (V,E)\) if \(Q_i\subset V\) for \(i\in \{1,2\}\), \(|Q_1 |\geq 2\) or \(|Q_2 |\geq 2\), \(|V \backslash (Q_1\cup Q_2) |\geq 2\) and every vertex \(v\in V\backslash (Q_1\cup Q_2)\) is adjacent to either all or none of the vertices of \(Q_i\), \(i\in \{1,2\}\). Homogeneous pairs are of interest in connection with the strong perfect graph conjecture---it is known that minimally imperfect graphs contain no homogeneous pair. This paper describes an \(O(mn^3)\) time bounded algorithm for determining whether a given graph contains a homogeneous pair, and, if possible, for finding one. Hereby \(n=|V|\) and \(m=|E|\).