Abstract
Color Coding is an algorithmic technique for deciding efficiently if a given input graph contains a path of a given length (or another small subgraph of constant tree-width). Applications of the method in computational biology motivate the study of similar algorithms for counting the number of copies of a given subgraph. While it is unlikely that exact counting of this type can be performed efficiently, as the problem is #W[1]-complete even for paths, approximate counting is possible, and leads to the investigation of an intriguing variant of families of perfect hash functions. A family of functions from [n] to [k] is an (ε,k)-balanced family of hash functions, if there exists a positive T so that for every K ⊂ [n] of size |K| = k, the number of functions in the family that are one-to-one on K is between (1 − ε)T and (1 + ε)T. The family is perfectly k-balanced if it is (0,k)-balanced.
We show that every such perfectly k-balanced family is of size at least \(c(k) n^{\lfloor k/2 \rfloor}\), and that for every \(\epsilon>\frac{1}{poly(k)}\) there are explicit constructions of (ε,k)-balanced families of hash functions from [n] to [k] of size e (1 + o(1))k logn. This is tight up to the o(1)-term in the exponent, and supplies deterministic polynomial time algorithms for approximately counting the number of paths or cycles of a specified length k (or copies of any graph H with k vertices and bounded tree-width) in a given input graph of size n, up to relative error ε, for all k ≤ O(logn).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms 7(4), 567–583 (1986)
Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F., Sahinalp, S.C.: Biomolecular network motif counting and discovery by color coding. In: ISMB (Supplement of Bioinformatics), pp. 241–249 (2008)
Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple construction of almost k-wise independent random variables. Random Struct. Algorithms 3(3), 289–304 (1992)
Alon, N., Gutner, S.: Balanced families of perfect hash functions and their applications. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 435–446. Springer, Heidelberg (2007)
Alon, N., Roichman, Y.: Random Cayley graphs and expanders. Random Struct. Algorithms 5(2), 271–285 (1994)
Alon, N., Schwartz, O., Shapira, A.: An elementary construction of constant-degree expanders. Combin. Probab. Comput. 17(3), 319–327 (2008)
Alon, N., Spencer, J.H.: The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., Hoboken (2008)
Alon, N., Yuster, R., Zwick, U.: Color-coding. Journal of the ACM 42(4), 844–856 (1995)
Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209–223 (1997)
Arvind, V., Raman, V.: Approximation algorithms for some parameterized counting problems. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 453–464. Springer, Heidelberg (2002)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Counting paths and packings in halves. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 578–586. Springer, Heidelberg (2009)
Feller, W.: An introduction to probability theory and its applications, 3rd edn., vol. I. Wiley, New York (1968)
Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM Journal on Computing 33(4), 892–922 (2004)
Fredman, M.L., Komlós, J., Szemerédi, E.: Storing a sparse table with O(1) worst case access time. Journal of the ACM 31(3), 538–544 (1984)
Hall Jr., M.: Combinatorial theory, 2nd edn. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons Inc., A Wiley-Interscience Publication, New York (1986)
Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Amer. Math. Soc (N.S.) 43(4), 439–561 (2006) (electronic)
Hüffner, F., Wernicke, S., Zichner, T.: Algorithm engineering for color-coding to facilitate signaling pathway detection. In: Sankoff, D., Wang, L., Chin, F. (eds.) APBC. Advances in Bioinformatics and Computational Biology, vol. 5, pp. 277–286. Imperial College Press (2007)
Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci 62(2), 367–375 (2001)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001)
Jukna, S.: Extremal combinatorics. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2001); With applications in computer science
Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, pp. 182–191 (1995)
Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM Journal on Computing 19(5), 775–786 (1990)
Scott, J., Ideker, T., Karp, R.M., Sharan, R.: Efficient algorithms for detecting signaling pathways in protein interaction networks. Journal of Computational Biology 13(2), 133–144 (2006)
Sharan, R., Ideker, T.: Modeling cellular machinery through biological network comparison. Nature Biotechnology 24(4), 427–433 (2006)
Shlomi, T., Segal, D., Ruppin, E., Sharan, R.: QPath: a method for querying pathways in a protein-protein interaction network. BMC Bioinformatics 7, 199 (2006)
Vassilevska, V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 455–464. ACM, New York (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alon, N., Gutner, S. (2009). Balanced Hashing, Color Coding and Approximate Counting. In: Chen, J., Fomin, F.V. (eds) Parameterized and Exact Computation. IWPEC 2009. Lecture Notes in Computer Science, vol 5917. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11269-0_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-11269-0_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11268-3
Online ISBN: 978-3-642-11269-0
eBook Packages: Computer ScienceComputer Science (R0)