Hostname: page-component-745bb68f8f-grxwn Total loading time: 0 Render date: 2025-02-06T22:32:04.907Z Has data issue: false hasContentIssue false
  • English
  • Français

Approximately Counting Embeddings into Random Graphs†

Published online by Cambridge University Press:  09 July 2014

MARTIN FÜRER  and
SHIVA PRASAD KASIVISWANATHAN
MARTIN FÜRER
Affiliation:
Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, 16802, USA (e-mail: furer@cse.psu.edu)
SHIVA PRASAD KASIVISWANATHAN
Affiliation:
General Electric Research, San Ramon, CA, 94568, USA (e-mail: kasivisw@gmail.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let H be a graph, and let CH(G) be the number of (subgraph isomorphic) copies of H contained in a graph G. We investigate the fundamental problem of estimating CH(G). Previous results cover only a few specific instances of this general problem, for example the case when H has degree at most one (the monomer-dimer problem). In this paper we present the first general subcase of the subgraph isomorphism counting problem, which is almost always efficiently approximable. The results rely on a new graph decomposition technique. Informally, the decomposition is a labelling of the vertices such that every edge is between vertices with different labels, and for every vertex all neighbours with a higher label have identical labels. The labelling implicitly generates a sequence of bipartite graphs, which permits us to break the problem of counting embeddings of large subgraphs into that of counting embeddings of small subgraphs. Using this method, we present a simple randomized algorithm for the counting problem. For all decomposable graphs H and all graphs G, the algorithm is an unbiased estimator. Furthermore, for all graphs H having a decomposition where each of the bipartite graphs generated is small and almost all graphs G, the algorithm is a fully polynomial randomized approximation scheme.

We show that the graph classes of H for which we obtain a fully polynomial randomized approximation scheme for almost all G includes graphs of degree at most two, bounded-degree forests, bounded-width grid graphs, subdivision of bounded-degree graphs, and major subclasses of outerplanar graphs, series-parallel graphs and planar graphs of large girth, whereas unbounded-width grid graphs are excluded. Moreover, our general technique can easily be applied to proving many more similar results.

Keywords

Primary 68W20Secondary 68Q87
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 6: Honouring the Memory of Philippe Flajolet - Part 2 , November 2014 , pp. 1028 - 1056
Copyright
Copyright © Cambridge University Press 2014 

Footnotes

†

A preliminary version of this paper appeared in the 12th International Workshop on Randomization and Computation (RANDOM 2008).

References

[1]Alon, N., Frieze, A. M. and Welsh, D. (1995) Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case. Random Struct. Alg. 6 459–478.Google Scholar
[2]Alon, N., Yuster, R. and Zwick, U. (1995) Color-coding. J. Assoc. Comput. Mach. 42 844–856.Google Scholar
[3]Artymiuk, P. J., Bath, P. A., Grindley, H., Pepperrell, M., Poirrette, C. A., Rice, A. R., Thorner, D. W., Wild, D. A., Willett, D. J., Allen, P., H., F., and Taylor, R. (1992) Similarity searching in databases of three-dimensional molecules and macromolecules. J. Chem. Inform. Comput. Sci. 32 617–630.Google Scholar
[4]Arvind, V. and Raman, V. (2002) Approximation algorithms for some parameterized counting problems. In Algorithms and Computation, Vol. 2518 of Lecture Notes in Computer Science, Springer, pp. 453–464.Google Scholar
[5]Bezáková, I., Bhatnagar, N. and Vigoda, E. (2007) (2006) Sampling binary contingency tables with a greedy start. Random Struct. Alg. 30 168–205.CrossRefGoogle Scholar
[6]Chien, S. (2004) A determinant-based algorithm for counting perfect matchings in a general graph. In Proc. 15th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 728–735.Google Scholar
[7]Diestel, R. (2000) Graph Theory, second edition, Springer.Google Scholar
[8]Dong, H., Wu, Y. and Ding, X. (1988) An ARG representation for Chinese characters and a radical extraction based on the representation. In International Conference on Pattern Recognition, IEEE, pp. 920–922.Google Scholar
[9]Dyer, M., Frieze, A. M. and Jerrum, M. (1998) Approximately counting Hamilton paths and cycles in dense graphs. SIAM J. Comput. 27 1262–1272.Google Scholar
[10]Erdős, P., and Rényi, A. (1960) On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5 17–61.Google Scholar
[11]Flum, J. and Grohe, M. (2004) The parameterized complexity of counting problems. SIAM J. Comput. 33 892–922.Google Scholar
[12]Frieze, A. M. and Jerrum, M. (1995) An analysis of a Monte Carlo algorithm for estimating the permanent. Combinatorica 15 67–83.Google Scholar
[13]Frieze, A. M., Jerrum, M., Molloy, M. K., Robinson, R. and Wormald, N. C. (1996) Generating and counting Hamilton cycles in random regular graphs. J. Algorithms 21 176–198.CrossRefGoogle Scholar
[14]Frieze, A. M. and McDiarmid, C. (1997) Algorithmic theory of random graphs. Random Struct. Alg. 10 5–42.3.0.CO;2-Z>CrossRefGoogle Scholar
[15]Frieze, A. M. and Suen, S. (1992) Counting the number of Hamilton cycles in random digraphs. Random Struct. Alg. 3 235–242.Google Scholar
[16]Fürer, M. and Kasiviswanathan, S. P. (2004) An almost linear time approximation algorithm for the permanent of a random (0–1) matrix. In Foundations of Software Technology and Theoretical Computer Science: FSTTCS 2004, Vol. 3328 of Lecture Notes in Computer Science, Springer, pp. 263–274.CrossRefGoogle Scholar
[17]Fürer, M. and Kasiviswanathan, S. P. (2005) Approximately counting perfect matchings in general graphs. In ALENEX/ANALCO, SIAM, pp. 263–272.Google Scholar
[18]Halin, R. (1971) Studies on minimally n-connected graphs. In Combinatorial Mathematics and its Applications (Welsh, D. J. A., ed.), Academic Press, pp. 129–136.Google Scholar
[19]Hammersley, J. M. (1966) Existence theorems and Monte Carlo methods for the monomer–dimer problem. Research Papers in Statistics, Wiley, London, 125–146.Google Scholar
[20]Heun, V. and Mayr, E. W. (2002) Embedding graphs with bounded treewidth into optimal hypercubes. J. Algorithms 43 17–50.Google Scholar
[21]Janson, S., Łuczak, T., and Ruciński, A. (2000) Random Graphs, Wiley-Interscience.Google Scholar
[22]Jerrum, M. (2003) Counting, Sampling and Integrating: Algorithms and Complexity, Birkhäuser.Google Scholar
[23]Jerrum, M. and Sinclair, A. (1989) Approximating the permanent. SIAM J. Comput. 18 1149–1178.Google Scholar
[24]Jerrum, M. and Sinclair, A. (1993) Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput. 22 1087–1116.Google Scholar
[25]Jerrum, M., Sinclair, A. and Vigoda, E. (2004) A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. Assoc. Comput. Mach. 51 671–697.Google Scholar
[26]Jerrum, M., Valiant, L. and Vazirani, V. (1986) Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43 169–188.CrossRefGoogle Scholar
[27]Kasteleyn, P. W. (1967) Graph Theory and Crystal Physics (Harary, F., ed.), Academic Press.Google Scholar
[28]Knuth, D. E. (1975) Estimating the efficiency of backtrack programs. Math. Comp. 29 121–136.CrossRefGoogle Scholar
[29]Levinson, R. (1992) Pattern associativity and the retrieval of semantic networks. Comput. Math. Appl. 23 573–600.Google Scholar
[30]Luks, E. M. (1982) Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25 42–65.Google Scholar
[31]Rasmussen, L. E. (1994) Approximating the permanent: A simple approach. Random Struct. Alg. 5 349–362.Google Scholar
[32]Rasmussen, L. E. (1997) Approximately counting cliques. Random Struct. Alg. 11 395–411.Google Scholar
[33]Riordan, O. (2000) Spanning subgraphs of random graphs. Combin. Probab. Comput. 9 125–148.Google Scholar
[34]Sankowski, P. (2003) Alternative algorithms for counting all matchings in graphs. In STACS, Vol. 2607 of Lecture Notes in Computer Science Volume, Springer, pp. 427–438.Google Scholar
[35]Stahs, T. and Wahl, F. M. (1992) Recognition of polyhedral objects under perspective views. Comput. Artificial Intelligence 11 155–172.Google Scholar
[36]Toda, S. (1989) On the computational power of PP and ⊕P. In FOCS, IEEE, pp. 514–519.Google Scholar
[37]Valiant, L. G. (1979) The complexity of computing the permanent. Theoret. Comput. Sci. 8 189–201.Google Scholar