<p>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?</p>

<p>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 <em>maximum</em>-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 <em>minimize</em> the total length of the node labels.</p>

<p><strong>Are the following problems NP-hard?</strong></p>

<ul>
<li><p><strong>Given a labeled graph $G$, find a sequence of legal contractions that minimizes the total length of all node labels in the resulting graph.</strong>  </p></li>
<li><p><strong>Given two labeled graphs $G$ and $H$, is there a sequence of legal contractions that transforms $G$ into $H$?</strong> </p></li>
</ul>

CC BY-SA 3.0
2012-07-01T03:26:38.003Z
could you define the problem more precisely? like give input and desired output?
Sasho Nikolov
CC BY-SA 3.0
2012-07-01T07:47:34.400Z
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ε
CC BY-SA 3.0
2012-07-01T14:24:10.070Z
I added more descriptions in bold fonts. Sorry for confusion.
Yinfang Zhuang
CC BY-SA 3.0
2012-07-01T20:32:25.770Z
Edited for clarity (I hope).
Jeffε
CC BY-SA 3.0
2012-07-01T20:49:38.573Z
Simultaneously posted on [math.SE (and migrated to CS.SE)](http://cs.stackexchange.com/questions/2573/np-completeness-proof).    Please don't do that.
Jeffε
CC BY-SA 3.0
2012-07-02T07:47:34.737Z
It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites).
Kaveh
<cc.complexity-theory><np-hardness><np>
Help with an np-completeness proof
Yinfang Zhuang
# Help with an np-completeness proof

(Asked by: username_0 on 2012-07-01)

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

**Tags:** cc.complexity-theory, np-hardness, np

> **Comments:**
> **username_1**: could you define the problem more precisely? like give input and desired output?  
> **username_2**: 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.  
> **username_0**: I added more descriptions in bold fonts. Sorry for confusion.  
> **username_2**: Edited for clarity (I hope).  
> **username_2**: Simultaneously posted on [math.SE (and migrated to CS.SE)](http://cs.stackexchange.com/questions/2573/np-completeness-proof).    Please don't do that.  
> **username_3**: It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites).  

---

## 0 answers

