Parameterized certificate dispersal and its variants

详细信息    查看全文

• 作者：Valentin Garnero ; ^{garnero@lirmm.fr" class="auth_mail" title="E-mail the corresponding author} ; Mathias Weller ; ¹ ; ^{weller@lirmm.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Asymmetric cryptography ; Algorithmic graph theory ; Parameterized complexity ; Turing kernelization
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：4 April 2016
• 年：2016
• 卷：622
• 期：Complete
• 页码：66-78
• 全文大小：482 K

文摘

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$(u,v)\in 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 W[1]-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$t\le 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.