On the complexity of overlaying a hypergraph with a graph with bounded maximum degree - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2021

On the complexity of overlaying a hypergraph with a graph with bounded maximum degree

(1) , (2) , (1, 2)
1
2

Abstract

Let G and H be respectively a graph and a hypergraph defined on a same set of vertices, and let F be a graph. We say that G F-overlays a hyperedge S of H if the subgraph of G induced by S contains F as a spanning subgraph, and that G F-overlays H if it F-overlays every hyperedge of H. For a fixed graph F and a fixed integer k, the problem (∆ ≤ k)-F-Overlay consists in deciding whether there exists a graph with maximum degree at most k that F-overlays a given hypergraph H. In this paper, we prove that for any graph F which is neither complete nor anticomplete, there exists an integer np(F) such that (∆ ≤ k)-F-Overlay is NP-complete for all k ≥ np(F).
Fichier principal
Vignette du fichier
article_appendice.pdf (636.46 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03368214 , version 1 (06-10-2021)
hal-03368214 , version 2 (11-01-2022)

Identifiers

  • HAL Id : hal-03368214 , version 2

Cite

Frédéric Havet, Dorian Mazauric, Viet-Ha Nguyen. On the complexity of overlaying a hypergraph with a graph with bounded maximum degree. [Research Report] Inria; CNRS; I3S; Université Côte d'Azur. 2021. ⟨hal-03368214v2⟩
27 View
49 Download

Share

Gmail Facebook Twitter LinkedIn More