Skip to Main content Skip to Navigation
Conference papers

Complexity Dichotomies for the Minimum $F$-Overlay Problem

Nathann Cohen 1 Frédéric Havet 2, 3 Dorian Mazauric 2, 4 Ignasi Sau Valls 5, 6 Rémi Watrigant 2, 4
1 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)
LRI - Laboratoire de Recherche en Informatique
3 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
4 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
5 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Dorian Mazauric Connect in order to contact the contributor
Submitted on : Tuesday, August 1, 2017 - 6:00:08 PM
Last modification on : Tuesday, January 4, 2022 - 4:31:46 AM


Files produced by the author(s)



Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau Valls, 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⟩



Les métriques sont temporairement indisponibles