Complexity issues for the sandwich homogeneous set problem

作     者：Durand, Arnaud Habib, Michel 

作者机构：LIAFA UMR 7089 CNRS F-75205 Paris 13 France Univ Paris 07 UFR Informat F-75205 Paris 13 France Equipe Log Math FRE 3233 CNRS F-75205 Paris 13 France Univ Paris 07 UFR Math F-75205 Paris 13 France 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2011年第159卷第7期

页      面：574-580页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：Graph sandwich problems Homogeneous sets Complexity of enumeration problems 

摘      要：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 Pi of graphs and two disjoint sets of edges E-1, E-2 with E-1 subset of E-2 on a vertex set V. the problem is to find a graph G on V with edge set E-s having property Pi and such that E-1 subset of E-s subset of E-2. In this paper, we exhibit a quasi-linear reduction between the problem of finding an independent set of size k = 2 in a graph and the problem of finding a sandwich homogeneous set of the same size 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. (C) 2010 Elsevier B.V. All rights reserved.