Hostname: page-component-76fb5796d-9pm4c Total loading time: 0 Render date: 2024-04-25T10:53:04.025Z 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)
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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