Complexity issues for the sandwich homogeneous set problem

Graph sandwich problems were introduced by Golumbic et al. (1994) in [12] for DNA physical mapping problems and can be described as follows. Given a property ΠΠ of graphs and two disjoint sets of edges E1E1, E2E2 with E1⊆E2E1⊆E2 on a vertex set VV, the problem is to find a graph GG on VV with edge set EsEs having property ΠΠ and such that E1⊆Es⊆E2E1⊆Es⊆E2.In this paper, we exhibit a quasi-linear reduction between the problem of finding an independent set of size k≥2k≥2 in a graph and the problem of finding a sandwich homogeneous set of the same size kk. Using this reduction, we prove that a number of natural (decision and counting) problems related to sandwich homogeneous sets are hard in general. We then exploit a little further the reduction and show that finding efficient algorithms to compute small sandwich homogeneous sets would imply substantial improvement for computing triangles in graphs.