Complexity Dichotomies for the Minimum $F$-Overlay Problem

Nathann Cohen 1 Frédéric Havet 2, 3 Dorian Mazauric 2, 4 Ignasi Sau 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
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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 metadatas

Cited literature [18 references]  Display  Hide  Download
Contributor : Dorian Mazauric <>
Submitted on : Tuesday, August 1, 2017 - 6:00:08 PM
Last modification on : Thursday, February 7, 2019 - 4:57:28 PM


Files produced by the author(s)


  • HAL Id : hal-01571229, version 1
  • ARXIV : 1703.05156


Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau, Rémi Watrigant. Complexity Dichotomies for the Minimum $F$-Overlay Problem. IWOCA: International Workshop on Combinatorial Algorithms, Jul 2017, Newcastle, Australia. pp.12. ⟨hal-01571229⟩



Record views


Files downloads