# Algorithm for finding mesh subgraphs?

I have a dense unlabeled graph ( each vertex has got at least 4 incident edges ).

Number of vertices (V) of the graph is always a perfect square.

I want to find all the meshes of $\sqrt{v} {x} \sqrt{v}$ in it.

Are there any known algorithms to accomplish this?

Any help is appreciated.

Thanks!

-

## 1 Answer

There could easily be an exponential number of meshes (e.g. let your graph be complete). And it's NP-complete to find even one of them (a graph G has a Hamiltonian path if and only the Cartesian product of G with a path contains a mesh).

So, yes, there are algorithms — you can just do a brute force search over all permutations of the vertices, for instance — but not polynomial algorithms.

-
Oh no! I have 256 nodes i.e. 256! possibilities. Yet another attempt to make a million dollars failed. Thanks! :D –  Pratik Deoghare Jul 14 '10 at 21:03