Polynomial-Time Data Reduction for the Subset Interconnection Design Problem

Abstract : The NP-hard Subset Interconnection Design problem, also known as Minimum Topic-Connected Overlay, is motivated by numerous applications including the design of scalable overlay networks and vacuum systems. It has as input a finite set V and a collection of subsets V 1 , V 2 ,. .. , Vm ⊆ V , and asks for a minimum-cardinality edge set E such that for the graph G = (V, E) all induced subgraphs G[V 1 ], G[V 2 ],. .. , G[Vm] are connected. We study Subset In-terconnection Design in the context of polynomial-time data reduction rules that preserve the possibility to construct optimal solutions. Our contribution is threefold: First, we show the incor-rectness of earlier polynomial-time data reduction rules. Second, we show linear-time solvability in case of a constant number m of subsets, implying fixed-parameter tractability for the parameter m. Third, we provide a fixed-parameter tractability result for small subset sizes and tree-like output graphs. To achieve our results, we elaborate on polynomial-time data reduction rules which also may be of practical use in solving Subset Interconnection Design.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2015, 29 (1), pp.1-25. 〈10.1137/140955057〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01349211
Contributeur : Isabelle Gouat <>
Soumis le : mercredi 27 juillet 2016 - 08:02:56
Dernière modification le : mercredi 10 octobre 2018 - 14:28:13

Fichier

Subset_Interconnection_Design-...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jiehua Chen, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge, Mathias Weller. Polynomial-Time Data Reduction for the Subset Interconnection Design Problem . Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2015, 29 (1), pp.1-25. 〈10.1137/140955057〉. 〈lirmm-01349211〉

Partager

Métriques

Consultations de la notice

270

Téléchargements de fichiers

267