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
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.
Type de document :
Communication dans un congrès
IWOCA 2017 - 28th International Workshop on Combinatorial Algorithms, Jul 2017, Newcastle, Australia. pp.12, 2017, 〈https://carma.newcastle.edu.au/meetings/iwoca/〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01571229
Contributeur : Dorian Mazauric <>
Soumis le : mardi 1 août 2017 - 18:00:08
Dernière modification le : lundi 9 octobre 2017 - 15:43:58

Fichier

iwoca2017-SUBMITTED.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01571229, version 1

Citation

Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau, Rémi Watrigant. Complexity Dichotomies for the Minimum F -Overlay Problem. IWOCA 2017 - 28th International Workshop on Combinatorial Algorithms, Jul 2017, Newcastle, Australia. pp.12, 2017, 〈https://carma.newcastle.edu.au/meetings/iwoca/〉. 〈hal-01571229〉

Partager

Métriques

Consultations de
la notice

161

Téléchargements du document

22