Approximately Counting Embeddings into Random Graphs†. (November 2014)

• Record Type: Journal Article
• Authors: FÜRER, MARTIN; KASIVISWANATHAN, SHIVA PRASAD; Broutin, Nicolas; Fill, James Allen; Nebel, Markus; Ward, Mark Daniel
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 6(2014:Nov.)
• Page Start: 1028
• Page End: 1056
• Publication Date: 2014-11
• Subjects: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000339
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>Let <italic>H</italic> be a graph, and let <italic>C<sub>H</sub></italic>(<italic>G</italic>) be the number of (subgraph isomorphic) copies of <italic>H</italic> contained in a graph <italic>G</italic>. We investigate the fundamental problem of estimating <italic>C<sub>H</sub></italic>(<italic>G</italic>). Previous results cover only a few specific instances of this general problem, for example the case when <italic>H</italic> 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 <italic>H</italic> and all graphs <italic>G</italic>, the algorithm is an unbiased estimator. Furthermore, for all graphs <italic>H</italic> having a decomposition where each of the bipartite graphs generated is small and almost all graphs <italic>G</italic>, the algorithm is a fully polynomial randomized approximation scheme.</p> <p>We show that the graph classes of <italic>H</italic> for which we obtain a fully polynomial randomized approximation scheme for almost all <italic>G</italic> 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.</p> </abstract>