Overlaying a hypergraph with a graph with bounded maximum degree

International audience; Let G be a graph and H a ​​hypergraph with the same set of vertices and let F be a fixed graph. The graph GF overlays a hyperedge S of H if F is a covering subgraph of the subgraph of G induced by S. The graph GF-overlaying H if F overlays each hyperedge of H. We have analyze the complexity of the following two problems. The first problem, ($∆ ≤ k$) F-OVERLAY, consists in deciding if there is a graph of maximum degree at most k which F overlays a given hypergraph H. This is a special case of the second problem, MAX ($∆ ≤ k$) F-OVERLAY, which, given a hypergraph H and an integer s, consists in deciding whether there is a graph of maximum degree at most k which F overlays at least s hyper edges of H. We prove a polynomial /NP-complete dichotomy for the MAX ($∆ ≤ k$) -F-OVERLAY, and prove the complexity of the problem ($∆ ≤ k$) F-OVERLAY for a large number of pairs (F, k). These two problems model a central problem in computational structural biology: the determination of the contacts between the proteins of a macromolecular assembly. The vertices are the proteins, the hyperedges are the known complexes, the graph F is the generic graph whose edges correspond to the contacts between the proteins of the assembly. Determining the graph G then comes down to finding the contacts between the proteins so that the graph F is a subgraph covering in each hyperedge and so that the degree is bounded (a protein is in contact with a limited number of others proteins). Finally, these problems are of more general interest for network inference problems.; Soient G un graphe et H un hypergraphe avec le même ensemble de sommets et soit F un graphe fixé. Le graphe GF-revouvre une hyperarête S de H si F est un sous-graphe couvrant du sous-graphe de G induit par S. Le graphe GF-revouvre H s’il F-revouvrechaque hyperarête de H. Nous avons analysé la complexité des deux problèmes suivants. Le premier problème, ($∆ ≤ k$) F-OVERLAY, consistè a décider s'il existe un graphe de degré maximum au plus k qui F-revouvre un hypergraphe H donné. C'est un cas particulier du second problème, MAX ($∆ ≤ k$) F-OVERLAY, qui,étant donné un hypergraphe H et un entier s, consistè a décider s'il existe un graphe de degré maximum au plus k qui F-revouvre au moins s hyperarêtes de H. Nous prouvons une dichotomie polynomial/N P-complet pour le problème MAX ($∆ ≤ k$)-F-OVERLAY dépendant de la paire (F, k), et prouvons la complexité du problème ($∆ ≤ k$) F-OVERLAY pour un grand nombre de paires (F, k). Ces deux problèmes modélisent un problème central en biologie structurale computationnelle : la détermination des contacts entre les protéines d'un assemblage macromoléculaire. Les sommets sont les protéines, les hyperarêtes sont les complexes connus, le graphe F est le graphe générique dont les arêtes correspondent aux contacts entre les protéines de l'assemblage. Déterminer le graphe G revient alorsà trouver les contacts entre les protéines de telle sorte que le graphe F soit un sous-graphe couvrant dans chaque hyperarête et de telle sorte que le degré soit borné (une protéine est en contact avec un nombre limité d'autres protéines). Enfin, ces problèmes sont d'intérêt plus général pour les problèmes d'inférence de réseaux.