Graph Contractability: NP-Complete or Not?

[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 ?

 

[chiro]

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 ?

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.

 

[yzhua3]

Thanks for your prompt reply !

In my problem each node is associated with some metric. At each step only a subset of edges are candidates for contracting or merging. Contracting one edge may affect the subset of edges that are legal for contracting at next step. By contracting one edge, we also replace the metrics of the two endpoint nodes with a new smaller metric. We are trying to find an H such that the sum of the metrics of nodes in H is minimal.

Any hint on whether this problem is NP-hard(NP-complete) or not. If so any hint on how to prove it ?

 

[yzhua3]

Here are more descriptions: Each node has a 0/1-string label. We define a function to measure the similarity between two labels of the adjacent nodes(i.e. the length of the common prefix of the two labels). At each step only the two adjacent nodes with maximal similarity can be merged (there may be several of them). After we merge the two nodes we label the new node with the common prefix of the original two labels. We also have to preserve the uniqueness of the label. We do no merge if it violates uniqueness of labels. We add up the length of the label of each node in the final graph and try to find the minimum of this number. Or in a more abstract sense, Is labeled graph G contractible (while maintaining our needed invariants e.g. uniqueness of labels) to (given) labeled graph H ?

 

[rezeew]

Based on your description, it sounds like your problem is a variation of the traditional graph contractability problem, where additional constraints are introduced after each edge contraction. This type of problem is known as a "restricted" or "constrained" version of a problem, and it is common for such variations to have different complexity classes than the original problem.

In this case, it is difficult to determine the complexity class of your problem without more information. It is possible that your problem is still NP-complete, or it may fall into a different complexity class such as P or NP-hard. To prove the complexity class of your problem, you can try reducing it to a known NP-complete problem or use other techniques such as approximation algorithms or parameterized complexity.

Overall, it is important to carefully define your problem and consider its specific constraints in order to determine its complexity class and potential solutions. Good luck with your research!