Overlaying a hypergraph with a graph with bounded maximum degree

Frédéric Havet 1 Dorian Mazauric 2 Viet-Ha Nguyen 1, 2 Rémi Watrigant 3
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
3 MC2 - Modèles de calcul, Complexité, Combinatoire
LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : 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).
Document type :
Reports
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-02025469
Contributor : Ha Nguyen <>
Submitted on : Tuesday, February 19, 2019 - 4:39:21 PM
Last modification on : Wednesday, April 3, 2019 - 1:30:22 AM
Long-term archiving on : Monday, May 20, 2019 - 5:18:51 PM

File

RR-9258.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02025469, version 1

Citation

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-02025469⟩

Share

Metrics

Record views

84

Files downloads

279