×

Randomised enumeration of small witnesses using a decision oracle. (English) Zbl 1411.68049

Summary: Many combinatorial problems involve determining whether a universe of \(n\) elements contains a witness consisting of \(k\) elements which have some specified property. In this paper we investigate the relationship between the decision and enumeration versions of such problems: efficient methods are known for transforming a decision algorithm into a search procedure that finds a single witness, but even finding a second witness is not so straightforward in general. We show that, if the decision version of the problem can be solved in time \(f(k) \cdot \operatorname{poly}(n)\), there is a randomised algorithm which enumerates all witnesses in time \(e^{k + o(k)} \cdot f(k) \cdot \operatorname{poly}(n) \cdot N\), where \(N\) is the total number of witnesses. If the decision version of the problem is solved by a randomised algorithm which may return false negatives, then the same method allows us to output a list of witnesses in which any given witness will be included with high probability. The enumeration algorithm also gives rise to an efficient algorithm to count the total number of witnesses when this number is small.

MSC:

68Q25 Analysis of algorithms and problem complexity
68R05 Combinatorics in computer science
68W20 Randomized algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844-856 (1995) · Zbl 0885.68116 · doi:10.1145/210332.210337
[2] Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F., Sahinalp, S.C.: Biomolecular network motif counting and discovery by color coding. Bioinformatics 24(13), 241-249 (2008) · doi:10.1093/bioinformatics/btn163
[3] Arvind, V., Raman, V.: Approximation algorithms for some parameterized counting problems, ISAAC 2002, LNCS, vol. 2518, pp. 453-464. Springer, Berlin (2002) · Zbl 1019.68135
[4] Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings. arXiv:1007.1161 (2010) · Zbl 1370.68321
[5] Björklund, A., Kaski, P., Kowalik, L.: Probably optimal graph motifs. In: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), LIPIcs, vol. 20, pp. 20-31, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2013) · Zbl 1354.68108
[6] Björklund, A., Kaski, P., Kowalik, Ł.: Fast witness extraction using a Decision Oracle. In: Schulz, A.S., Wagner, D. (eds.) Algorithms-ESA 2014. ESA 2014. Lecture Notes in Computer Science, vol. 8737. Springer, Berlin, Heidelberg (2014) · Zbl 1423.68203
[7] Björklund, A., Kaski, P., Kowalik, L., Lauri, J.: Engineering motif search for large graphs. In: Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX 2015), SIAM, 2015, pp. 104-118 (2015) · Zbl 1429.68177
[8] Creignou, N., Ktari, R., Meier, A., Müller, J.S., Olive, F., Vollmer, H.: Parameterized enumeration for modification problems. In: Dediu, A.H., Formenti, E., Martín-Vide, C., Truthe, B. (eds.) Language and Automata Theory and Applications, LATA 2015. Lecture Notes in Computer Science, vol. 8977. Springer, Cham (2015) · Zbl 1451.68136
[9] Creignou, N., Meier, A., Müller, J.S., Schmidt, J., Vollmer, H.: Paradigms for parameterized enumeration. In: Chatterjee, K., Sgall, J. (eds.) Mathematical Foundations of Computer Science 2013, MFCS 2013. Lecture Notes in Computer Science, vol. 8087. Springer, Berlin, Heidelberg (2013) · Zbl 1362.68103
[10] Curticapean, R.: Counting Matchings of Size k is #W[1]-hard. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) Automata, Languages, and Programming. ICALP 2013. Lecture Notes in Computer Science, vol. 7965. Springer, Berlin, Heidelberg (2013) · Zbl 1336.68096
[11] Curticapean, R., Marx, D.: Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts. In: 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014)
[12] Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, London (2013) · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1
[13] Fernau, H.: On parameterized enumeration. In: Ibarra, O.H., Zhang, L. (eds.) Computing and combinatorics. COCOON 2002. Lecture Notes in Computer Science, vol. 2387. Springer, Berlin, Heidelberg (2002) · Zbl 1077.68658
[14] Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892-922 (2004) · Zbl 1105.68042 · doi:10.1137/S0097539703427203
[15] Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006) · Zbl 1143.68016
[16] Gelbord, B.: Graphical techniques in intrusion detection systems. In: Proceedings of 15th International Conference on Information Networking, pp. 253-258 (2001)
[17] Jerrum, M., Meeks, K.: The parameterised complexity of counting even and odd induced subgraphs. Combinatorica (2016). https://doi.org/10.1007/s00493-016-3338-5 · Zbl 1320.68101
[18] Jerrum, M., Meeks, K.: The parameterised complexity of counting connected subgraphs and graph motifs. J. Comput. Syst. Sci. 81(4), 702-716 (2015) · Zbl 1320.68101 · doi:10.1016/j.jcss.2014.11.015
[19] Jerrum, M., Meeks, K.: Some hard families of parameterised counting problems. ACM Trans. Comput. Theory 7(3), 11 (2015) · Zbl 1348.68066 · doi:10.1145/2786017
[20] Khuller, S., Vazirani, V.V.: Planar graph coloring is not self-reducible, assuming \[P \ne \]≠ NP. Theor. Comput. Sci. 88(1), 183-189 (1991) · Zbl 0729.05019 · doi:10.1016/0304-3975(91)90081-C
[21] Lawler, E.L.: A procedure for computing the \[k\] k best solutions to discrete optimization problems and its application to the shortest path problem. Manag. Sci. 18(7), 401-405 (1972) · Zbl 0234.90050 · doi:10.1287/mnsc.18.7.401
[22] Meeks, K.: The challenges of unbounded treewidth in parameterised subgraph counting problems. Discrete Appl. Math. 198, 170-194 (2016) · Zbl 1327.05244 · doi:10.1016/j.dam.2015.06.019
[23] Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: simple building blocks of complex networks. Science 298(5594), 824-827 (2002) · doi:10.1126/science.298.5594.824
[24] Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proceedings of IEEE 36th Annual Foundations of Computer Science (FOCS 1995), Milwaukee, WI, 1995, pp. 182-191. https://doi.org/10.1109/SFCS.1995.492475 · Zbl 0938.68932
[25] Sekar, V., Xie, Y., Maltz, D.A., Reiter, M.K., Zhang, H.: Toward a framework for internet forensic analysis. In: Third Workshop on Hot Topics in Networking (HotNets-III) (2004)
[26] Staniford-Chen, S., Cheung, S., Crawford, R., Dilger, M., Frank, J., Hoagland, J., Levitt, K., Wee, C., Yip, R., Zerkle, D.: GrIDS—a graph based intrusion detection system for large networks. In: Proceedings of the 19th National Information Systems Security Conference, pp. 361-370 (1996)
[27] Schnorr, C.P.: Optimal algorithms for self-reducible problems. In: Proceedings of the 3rd ICALP, Edinburgh University Press, pp. 322 - 337 (1976)
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.