An Efficient Algorithm for Solving the Homogeneous Set Sandwich Problem

Abstract

A set H of vertices of graph G(V,E) is a homogeneous set if each vertex in V\H is either adjacent to all vertices of H or to none of the vertices in H, where V and E are the vertex and edge, respectively, sets of graph G. A graph Gs(V,Es) is called a sandwich graph for the pair of graphs G(V,E)and Gt(V,Et) if Et≦Es≦E. The homogeneous set sandwich problem is to determine whether there exists a sandwich graph for the pair of graphs G and Gt such that there is a homogeneous set in Gs. In this paper, we shall propose an O(n3) time algorithm for solving the homogeneous set sandwich problem.