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


closed as not constructive by Jeffε, Tsuyoshi Ito, Kaveh Jul 2 '12 at 7:46

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ could you define the problem more precisely? like give input and desired output? $\endgroup$ – Sasho Nikolov Jul 1 '12 at 3:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Jeffε Jul 1 '12 at 7:47
  • $\begingroup$ I added more descriptions in bold fonts. Sorry for confusion. $\endgroup$ – Yinfang Zhuang Jul 1 '12 at 14:24
  • $\begingroup$ Edited for clarity (I hope). $\endgroup$ – Jeffε Jul 1 '12 at 20:32
  • 4
    $\begingroup$ Simultaneously posted on math.SE (and migrated to CS.SE). Please don't do that. $\endgroup$ – Jeffε Jul 1 '12 at 20:49