Skip to Main content Skip to Navigation
Conference papers

Overlaying a hypergraph with a graph with bounded maximum degree

Frédéric Havet 1 Dorian Mazauric 2 Viet-Ha Nguyen 1 Rémi Watrigant 3
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
2 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
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/N P-complete dichotomy for the Max (∆ ≤ k)-F-Overlay problems depending on the pairs (F, k), and establish the complexity of (∆ ≤ k) F-Overlay for many pairs (F, k).
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-03035849
Contributor : Frederic Havet <>
Submitted on : Wednesday, December 2, 2020 - 1:24:59 PM
Last modification on : Wednesday, December 9, 2020 - 11:02:57 AM

File

CALDAM-12pages.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03035849, 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. CALDAM 2020 - 6th Annual International Conference on Algorithms and Discrete Applied Mathematics, Feb 2020, Hyderabad, India. ⟨hal-03035849⟩

Share

Metrics

Record views

13

Files downloads

42