The Pair Completion algorithm for the Homogeneous Set Sandwich Problem

A homogeneous set is a non-trivial module of a graph, i.e., a non-empty, non-unitary, proper vertex subset such that all its elements present the same outer neighborhood. Given two graphs G1(V,E1) and G2(V,E2), the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a graph GS(V,ES), E1⊆ES⊆E2, which has a homogeneous set. This paper presents an algorithm that uses the concept of bias graph [S. Tang, F. Yeh, Y. Wang, An efficient algorithm for solving the homogeneous set sandwich problem, Inform. Process. Lett. 77 (2001) 17–22] to solve the problem in time, thus outperforming the other known HSSP deterministic algorithms for inputs where .