×

Parameterized certificate dispersal and its variants. (English) Zbl 1335.68104

Summary: 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) \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 \leq 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.

MSC:

68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms (graph-theoretic aspects)
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abu-Khzam, F. N.; Fellows, M. R.; Langston, M. A.; Suters, W. H., Crown structures for Vertex Cover kernelization, Theoret. Comput. Sci., 41, 3, 411-430 (2007) · Zbl 1148.68035
[2] Agrawal, A.; Klein, P. N.; Ravi, R., When trees collide: an approximation algorithm for the generalized Steiner problem on networks, SIAM J. Comput., 24, 3, 440-456 (1995) · Zbl 0831.68071
[3] Armstrong, D. E.; Jacobson, S. H., Studying the complexity of global verification for NP-hard discrete optimization problems, J. Global Optim., 27, 1, 83-96 (2003) · Zbl 1035.90112
[4] Binkele-Raible, D.; Fernau, H.; Fomin, F. V.; Lokshtanov, D.; Saurabh, S.; Villanger, Y., Kernel(s) for problems with no kernel: on out-trees with many leaves, ACM Trans. Algorithms, 8, 4, 38:1-38:19 (2012) · Zbl 1295.68120
[5] Bodlaender, H. L.; Jansen, B. M.P.; Kratsch, S., Kernelization lower bounds by cross-composition, SIAM J. Discrete Math., 28, 1, 277-305 (2014) · Zbl 1295.05222
[6] Cesati, M., The Turing way to parameterized complexity, J. Comput. System Sci., 67, 4, 654-685 (2003) · Zbl 1114.68045
[7] Chartrand, G.; Erwin, D.; Raines, M.; Zhang, P., Strong distance in strong digraphs, J. Combin. Math. Combin. Comput., 31, 33-44 (1999) · Zbl 0938.05029
[8] Cheung, W. C.; Goemans, M. X.; Wong, S. C., Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs, (Chekuri, C., Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 (2014), SIAM), 1714-1726 · Zbl 1421.68203
[9] Chor, B.; Fellows, M. R.; Juedes, D., Linear kernels in linear time, or how to save \(k\) colors in \(O(n^2)\) steps, (Proceedings, 30th International Workshop on Graph Theoretic Concepts in Computer Science. Proceedings, 30th International Workshop on Graph Theoretic Concepts in Computer Science, WG’04. Proceedings, 30th International Workshop on Graph Theoretic Concepts in Computer Science. Proceedings, 30th International Workshop on Graph Theoretic Concepts in Computer Science, WG’04, LNCS, vol. 3353 (2004), Springer), 257-269 · Zbl 1112.68412
[10] Cygan, M.; Kortsarz, G.; Nutov, Z., Steiner forest orientation problems, J. Discrete Math., 27, 3, 1503-1513 (2013) · Zbl 1283.05257
[11] Dankelmann, P.; Swart, H. C.; Day, D. P., On strong distances in oriented graphs, Discrete Math., 266, 1-3, 195-201 (2003) · Zbl 1025.05020
[12] Dell, H.; Marx, D., Kernelization of packing problems, (Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’12 (2012), SIAM), 68-81 · Zbl 1421.68072
[13] Downey, R. G.; Fellows, M. R., Fundamentals of Parameterized Complexity, Texts in Computer Science (2013), Springer · Zbl 1358.68006
[14] Feldman, J.; Ruhl, M., The directed Steiner network problem is tractable for a constant number of terminals, SIAM J. Comput., 36, 2, 543-561 (2006) · Zbl 1118.05039
[15] Ferguson, N.; Schneier, B., Practical Cryptography (2003), Wiley · Zbl 1314.94002
[16] Flum, J.; Grohe, M., Parameterized Complexity Theory, Texts in Theoretical Computer Science (2006), Springer
[17] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman · Zbl 0411.68039
[18] Hermelin, D.; Kratsch, S.; Soltys, K.; Wahlström, M.; Wu, X., A completeness theory for polynomial (Turing) kernelization, Algorithmica, 71, 3, 702-730 (2015) · Zbl 1312.68102
[19] Izumi, T.; Izumi, T.; Ono, H.; Wada, K., Approximability and inapproximability of the minimum certificate dispersal problem, Theoret. Comput. Sci., 411, 31-33, 2773-2783 (2010) · Zbl 1192.68907
[20] Izumi, T.; Izumi, T.; Ono, H.; Wada, K., Approximability of minimum certificate dispersal with tree structures, Theoret. Comput. Sci., 591, 5-14 (2015) · Zbl 1322.68143
[21] Jansen, B. M.P., Turing kernelization for finding long paths and cycles in restricted graph classes, (Proceedings of the 22nd Annual European Symposium on Algorithms. Proceedings of the 22nd Annual European Symposium on Algorithms, ESA’14. Proceedings of the 22nd Annual European Symposium on Algorithms. Proceedings of the 22nd Annual European Symposium on Algorithms, ESA’14, LNCS, vol. 8737 (2014), Springer), 579-591 · Zbl 1425.68144
[22] Juan, J. S.; Huang, C.-M., The strong distance problems, (Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA ’04 (2004), CSREA Press), 699-708
[23] Jung, E.; Elmallah, E. S.; Gouda, M. G., Optimal dispersal of certificate chains, IEEE Trans. Parallel Distrib. Syst., 18, 4, 474-484 (2007)
[24] Kratsch, S., Recent developments in kernelization: a survey, Bull. EATCS, 113 (2014) · Zbl 1409.68144
[25] Li, C.; McCormick, S. T.; Simchi-Levi, D., The point-to-point delivery and connection problems: complexity and algorithms, Discrete Appl. Math., 36, 3, 267-292 (1992) · Zbl 0761.68022
[26] Lokshtanov, D., New methods in parameterized algorithms and complexity (April 2009), University of Bergen: University of Bergen Norway, PhD thesis
[27] Natu, M.; Fang, S., The point-to-point connection problem - analysis and algorithms, Discrete Appl. Math., 78, 1-3, 207-226 (1997) · Zbl 0890.68104
[28] Nemhauser, G. L.; Trotter, L. E., Vertex packings: structural properties and algorithms, Math. Program., 8, 1, 232-248 (1975) · Zbl 0314.90059
[29] Niedermeier, R., Invitation to Fixed Parameter Algorithms, vol. 31 (2006), Oxford University Press · Zbl 1095.68038
[30] Thomassé, S.; Trotignon, N.; Vuskovic, K., A polynomial Turing-kernel for weighted independent set in bull-free graphs, (Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG’14. Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG’14, LNCS, vol. 8747 (2014), Springer), 408-419 · Zbl 1364.68232
[31] Weller, M., Aspects of preprocessing applied to combinatorial graph problems (February 2013), Technische Universität Berlin: Technische Universität Berlin Germany, PhD thesis
[32] Zheng, H.; Omura, S.; Uchida, J.; Wada, K., An optimal certificate dispersal algorithm for mobile ad hoc networks, IEICE Trans., 88-A, 5, 1258-1266 (2005)
[33] Zheng, H.; Omura, S.; Wada, K., An approximation algorithm for minimum certificate dispersal problems, IEICE Trans., 89-A, 2, 551-558 (2006)
[34] Zimmermann, P., PGP user’s guide, volume I: essential topics (1994), URL
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.