I know that graph contractability is NP-complete: 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?
Consider the following variant of the contractibility problem. Each node in the input graph is labeled with a unique bit-string of arbitrary length. The similarity of two nodes is defined to be the length of the longest common prefix of their labels; the weight of an edge is the similarity between its endpoints. At each step, we are allowed contract any maximum-weight edge $(u,v)$ and label the new node with the longest common prefix of the labels of $u$ and $v$. (There may be several maximum-weight edges.) However, we must also preserve label uniqueness; if some other node already has the new label, we cannot contract the edge $(u,v)$. Our goal is to minimize the total length of the node labels.
Are the following problems NP-hard?
Given a labeled graph $G$, find a sequence of legal contractions that minimizes the total length of all node labels in the resulting graph.
Given two labeled graphs $G$ and $H$, is there a sequence of legal contractions that transforms $G$ into $H$?