Complexity issues for the sandwich homogeneous set problem
Graph sandwich problems were introduced by Golumbic etal. (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 E1 E 1 , E2 E 2 with E1?E2 E 1 ? E 2 on a vertex set V V , the problem is to find a graph G G on V V with edge set Es E s having property ? ? and such that E1?Es?E2 E 1 ? E s ? E 2 . In this paper, we exhibit a quasi-linear reduction between the problem of finding an independent set of size k?2 k ? 2 in a graph and the problem of finding a sandwich homogeneous set of the same size k k . 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.
homogeneous sets graph sandwich problems complexity of enumeration problems