2
$\begingroup$

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

$\endgroup$
  • $\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