# Homework Help: NP-complete or not

1. Jun 29, 2012

### yzhua3

I know that graph contractability is NP-complete. To be specific given G=(V1,E1) and H=(V2,E2), can a graph isomorphic to H be obtained from G by a sequence of edge contractions ?

However my problem is a little bit different from the traditional graph contractability. In the traditional graph contractability problem we contract the original graph by different sequences of edge mergings. However in my problem after one edge is picked and merged, some edges are excluded from further merging. Any hint on whether this problem is NP-complete or not. If so any hint on how to prove it ?

2. Jun 30, 2012

### chiro

Hey yzhua3 and welcome to the forums.

For this you have to first consider whether you can get an isomorphism or not with contraction.

One suggestion for this is to use set theory. I'm going to assume your graph has no directed edges and that all edges are undirected.

The idea is the following: for each vertex in H you need to assign a vertex in G so that it has the potential to be collapsed to some vertex in H where it has the same number of edges. In other words, you first check without any notion of the actual topology of the graph whether you can even have an ismorphism with the right number of edges regardless of a contraction.

In the process you make a table of the number of vertices in G in terms of edges (again without topology).

From this you look at what I would call 'local' ismorphisms and do it recursively. A local isomorphism is an isomorphism of a subset of your original graph H. The first step establishes that you can have a local ismorphism and the process essentially expands the isomorphisms out with more vertices by merging ones that are 'successful' sub-isomorphisms together which then slowly as they expand either generate the candidates for the topology of the graph or reject any candidates.

If an isomorphism exists then the topologies starting from the individual node candidates (isolated vertices without a topology) will converge to the full isomorphism of G with the constraint of edge contractions to H.

First I will get your feedback on this suggestion and I acknowledge that it is not complete with regard to specific implementations in relation to being the optimal algorithm, but hopefully it's given you some food for thought.

3. Jun 30, 2012