Complexity Dichotomies for the Minimum $F$-Overlay Problem - Archive ouverte HAL Access content directly
Conference Papers Year : 2018

Complexity Dichotomies for the Minimum $F$-Overlay Problem


For a (possibly infinite) fixed family of graphs F, we say that a graph G overlays F on a hypergraph H if V (H) is equal to V (G) and the subgraph of G induced by every hyperedge of H contains some member of F as a spanning subgraph. While it is easy to see that the complete graph on |V (H)| overlays F on a hypergraph H whenever the problem admits a solution, the Minimum F-Overlay problem asks for such a graph with the minimum number of edges. This problem allows to generalize some natural problems which may arise in practice. For instance, if the family F contains all connected graphs, then Minimum F-Overlay corresponds to the Minimum Connectivity Inference problem (also known as Subset Interconnection Design problem) introduced for the low-resolution reconstruction of macro-molecular assembly in structural biology, or for the design of networks. Our main contribution is a strong dichotomy result regarding the polynomial vs. NP-hard status with respect to the considered family F. Roughly speaking, we show that the easy cases one can think of (e.g. when edge-less graphs of the right sizes are in F, or if F contains only cliques) are the only families giving rise to a polynomial problem: all others are NP-complete. We then investigate the parameterized complexity of the problem and give similar sufficient conditions on F that give rise to W[1]-hard, W[2]-hard or FPT problems when the parameter is the size of the solution. This yields an FPT/W[1]-hard dichotomy for a relaxed problem , where every hyperedge of H must contain some member of F as a (non necessarily spanning) subgraph.
Fichier principal
Vignette du fichier
iwoca2017-SUBMITTED.pdf (323.55 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01571229 , version 1 (01-08-2017)



Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau, Rémi Watrigant. Complexity Dichotomies for the Minimum $F$-Overlay Problem. 28th International Workshop on Combinatorial Algorithms (IWOCA), Jul 2017, Newcastle, Australia. pp.116-127, ⟨10.1007/978-3-319-78825-8_10⟩. ⟨hal-01571229⟩
770 View
193 Download



Gmail Facebook Twitter LinkedIn More