Approximately Counting Embeddings into Random Graphs

Details Approximately Counting Embeddings into Random Graphs Approximately Counting Embeddings into Random Graphs

2008-06-13

arxiv.org/abs/0806.2287v1

Computer Science

Data Structures and Algorithms

To appear in the proceedings of RANDOM 2008

Scientific paper

Let H be a graph, and let C(H,G) be the number of (subgraph isomorphic) copies of H contained in a graph G. We investigate the fundamental problem of estimating C(H,G). Previous results cover only a few specific instances of this general problem, for example, the case when H has degree at most one (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 labeling of the vertices generating a sequence of bipartite graphs. The decomposition 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, whereas unbounded-width grid graphs are excluded. Additionally, our general technique can easily be applied to proving many more similar results.

Affiliated with

Also associated with

No associations

Rating

Approximately Counting Embeddings into Random Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximately Counting Embeddings into Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximately Counting Embeddings into Random Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-123654