| Autor: |
Havet, Frédéric, Mazauric, Dorian, Nguyen, Viet-Ha, Watrigant, Rémi |
| Přispěvatelé: |
Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Algorithms, Biology, Structure (ABS), Inria Sophia Antipolis - Méditerranée (CRISAM), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis |
| Jazyk: |
angličtina |
| Rok vydání: |
2019 |
| Předmět: |
|
| Zdroj: |
[Research Report] RR-9258, Inria Sophia Antipolis. 2019 |
| Popis: |
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). |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
