Idioma:

Overlaying a hypergraph with a graph with bounded maximum degree

Havet, Frédéric ; Mazauric, Dorian ; Nguyen, Viet-Ha ; Watrigant, Rémi

Discrete Applied Mathematics, 2022-10, Vol.319, p.394-406 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Overlaying a hypergraph with a graph with bounded maximum degree
Autor: Havet, Frédéric ; Mazauric, Dorian ; Nguyen, Viet-Ha ; Watrigant, Rémi
Assuntos: Algorithm ; Complexity ; Computational structural biology ; Graphs ; Hypergraphs
É parte de: Discrete Applied Mathematics, 2022-10, Vol.319, p.394-406
Descrição: 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 GF-overlays a hyperedge S of H if F is a spanning subgraph of the subgraph of G induced by S, and that GF-overlaysH 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 problems depending on the pairs (F,k), and establish the complexity of (Δ≤k)F-Overlay for many pairs (F,k).
Editor: Elsevier B.V
Idioma: Inglês

Voltar para lista de resultados