I know that graph contractability is $NP$-complete. To be specific given $G=(V_1,E_1)$ and $H=(V_2,E_2)$, 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 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 ?
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 ?