Parameterized certificate dispersal and its variants

Valentin Garnero 1 Mathias Weller 2, 3
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Given a directed graph G and a set R of vertex pairs, the Minimum Certificate Dispersal problem asks for an assignment of arcs to vertices ("terminals") such that, for each ( u , v ) ¿ R , a u-v-path can be constructed using only arcs assigned to u or v. Herein, the total number k of assignments should be minimal. The problem is well motivated in key-exchange protocols for asymmetric cryptography. We provide a first parameterized complexity analysis of this NP-hard problem and its variant ChainedMinimum Certificate Dispersal, where, instead of pairs of terminals, a set of paths ("chains") that should be constructed, is prescribed.Although polynomial-time solvable for constant values of k, the former variant seems much harder, surfacing in the proof that it is W1-hard with respect to k while ChainedMinimum Certificate Dispersal yields a polynomial-size problem kernel. We even show fixed-parameter tractability of the latter with respect to the stronger parameter "number t of terminals". In particular, while there is no polynomial-size kernel with respect to t, the problem admits a polynomial-size Turing kernel. Towards answering the question whether Minimum Certificate Dispersal can be solved in polynomial time when t is constant, we show polynomial-time solvability for at most two requests (comprising all instances with t ¿ 2 ) using an algorithm for the Strong Distance problem, which asks for a minimum-size subdigraph in which two given vertices are strongly connected. Finally, we emphasize the hardness of Minimum Certificate Dispersal by proving it NP-hard for very restricted sets of instances, thereby excluding many parameters and combinations from consideration for efficient multivariate algorithms.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2016, 622, pp.66-78. 〈10.1016/j.tcs.2016.02.001〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01348417
Contributeur : Isabelle Gouat <>
Soumis le : samedi 23 juillet 2016 - 10:20:48
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

Collections

Citation

Valentin Garnero, Mathias Weller. Parameterized certificate dispersal and its variants. Theoretical Computer Science, Elsevier, 2016, 622, pp.66-78. 〈10.1016/j.tcs.2016.02.001〉. 〈lirmm-01348417〉

Partager

Métriques

Consultations de la notice

111