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 G(1) (V, E-1) and G(2)(V, E-2), the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a graph G(S)(V, E-S), E-1 subset of E-S subset of E-2, 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 O(n min{vertical bar E-1 vertical bar, vertical bar(E) over bar (2)vertical bar} log n) time, thus outperforming the other known HSSP deterministic algorithms for inputs where max{vertical bar E-1 vertical bar, vertical bar(E) over bar (2)vertical bar} = Omega (n log n). (c) 2006 Elsevier B.V. All fights reserved.
analysis of algorithms graph algorithms