Overlaying a hypergraph with a graph with bounded maximum degree - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2019

Overlaying a hypergraph with a graph with bounded maximum degree

Couvrant d’un hypergraphe avec un graphique à degré maximal borné

Résumé

Let G and H be respectively a graph and a hypergraph defined on a same set of vertices, and let F be a fixed graph. We say that G F -overlays a hyperedge S of H if F is a spanning subgraph of the subgraph of G induced by S, and that it F -overlays H if it F -overlays every hyperedge of H. Motivated by structural biology, we study the computational complexity of two problems. The first problem, (∆ ≤ k) F -Overlay, consists in deciding whether there is a graph with maximum degree at most k that F -overlays a given hypergraph H. It is a particular case of the second problem Max (∆ ≤ k) F -Overlay, which takes a hypergraph H and an integer s as input, and consists in deciding whether there is a graph with maximum degree at most k that F -overlays at least s hyperedges of H. We give a complete polynomial/NP-complete dichotomy for the Max (∆ ≤ k)-F -Overlay prob-lems depending on the pairs (F, k), and establish the complexity of (∆ ≤ k) F -Overlay for many pairs (F, k).
Soit G et H respectivement un graphe et un hypergraphe défini sur un même ensemble de sommets, et F un graphe fixé. Nous disons que G F -couvre un hyperedge S de H si F est un sous-graphe couvrant du sous-graphe de G induit par S, et qu’il le F - couvre H si F recouvre chaque hyperedge de H. Motivés par la biologie structurale, nous étudions la complexité algorithmique de deux problèmes. Le premier problème, (∆ ≤ k) F -Overlay, consiste à décider s’il existe ou non un graphe avec un degré maximum égal à k qui F couvre un hypergraphe H. C’est un cas particulier du deuxième probléme Max (∆ ≤ k) F -Overlay, qui prend en entrée un hypergraphe H et un entier s, et consiste à décider s’il y a un graphe avec degré maximum d’au plus k que F -couvre au moins s hyperges de H. Nous donnons une dichotomie complète polynomiale/NP-complète pour les problemes Max (∆ ≤ k)-F -Overlay en fonction des paires (F, k), et la complexité de (∆ ≤ k) F -Overlay pour plusieurs paires (F, k).
Fichier principal
Vignette du fichier
RR-9258.pdf (878.56 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02025469 , version 1 (19-02-2019)
hal-02025469 , version 2 (12-04-2020)
hal-02025469 , version 3 (26-07-2023)

Identifiants

  • HAL Id : hal-02025469 , version 1

Citer

Frédéric Havet, Dorian Mazauric, Viet-Ha Nguyen, Rémi Watrigant. Overlaying a hypergraph with a graph with bounded maximum degree. [Research Report] RR-9258, Inria Sophia Antipolis. 2019. ⟨hal-02025469v1⟩
210 Consultations
464 Téléchargements

Partager

Gmail Facebook X LinkedIn More