# Help with an np-completeness proof [closed]

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

• could you define the problem more precisely? like give input and desired output? – Sasho Nikolov Jul 1 '12 at 3:26
• Is H a graph? Is it part of the input? What does "the sum of the metrics" mean? (Under their usual definition, metrics are not numbers.) Without a precise description HOW the metrics are updated, I don't think this question can be answered even in principle. – Jeffε Jul 1 '12 at 7:47
• I added more descriptions in bold fonts. Sorry for confusion. – Yinfang Zhuang Jul 1 '12 at 14:24
• Edited for clarity (I hope). – Jeffε Jul 1 '12 at 20:32
• Simultaneously posted on math.SE (and migrated to CS.SE). Please don't do that. – Jeffε Jul 1 '12 at 20:49