Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Complexity Dichotomies for the Minimum F-Overlay Problem

Nathann Cohen 1 Frédéric Havet 2, 3 Dorian Mazauric 3, 4 Ignasi Sau Valls 5, 6 Rémi Watrigant 3, 4 
2 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
6 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 edgeless 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
Contributor : Dorian Mazauric Connect in order to contact the contributor
Submitted on : Wednesday, March 15, 2017 - 2:45:06 PM
Last modification on : Wednesday, October 26, 2022 - 8:14:26 AM
Long-term archiving on: : Friday, June 16, 2017 - 2:09:59 PM


Files produced by the author(s)


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


Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau Valls, Rémi Watrigant. Complexity Dichotomies for the Minimum F-Overlay Problem. [Research Report] RR-9045, Inria Sophia Antipolis. 2013, pp.16. ⟨hal-01490535⟩



Record views


Files downloads