Algorithms 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 subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs G(1)(V, E-1), G(2)(V, E-2), the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a sandwich graph G(S) (V, E-S), E-1 subset of E-S subset of E-2, which has a homogeneous set. In 2001 Tang et al. [ 15] published an all-fast O(n(2)Delta(2)) algorithm which was recently proven wrong [ 5], so that the HSSP's known upper bound would have been reset thereafter at the former O(n(4)) determined by Cerioli et al. [ 1] in 1998. We present, notwithstanding, new deterministic algorithms which have it established at O(n(3) log(m/n)). We give as well two even faster O(n(3)) randomized algorithms, whose simplicity might lend them didactic usefulness. We believe that, besides providing efficient easy-to-implement procedures to solve it, the study of these new approaches allows a fairly thorough understanding of the problem.
homogeneous set sandwich problem analysis of algorithms and problem complexity graph theory graph algorithms