Skip to Main content Skip to Navigation
Reports

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 [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-02025469
Contributor : Ha Nguyen <>
Submitted on : Sunday, April 12, 2020 - 10:53:12 AM
Last modification on : Monday, October 12, 2020 - 10:30:40 AM

File

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

Identifiers

  • HAL Id : hal-02025469, version 2

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

Share

Metrics

Record views

68

Files downloads

261