4
$\begingroup$

Duplicate:
NP-completeness of graph isomorphism through edge contractions with an edge validity condition

I know that graph contractability is $NP$-complete. To be specific 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 ?

However my problem is a little bit different from the traditional graph contractability. In the traditional graph contractability problem we contract the original graph by different sequences of edge mergings. However in my problem each node is associated with some metric. At each step only a subset of edges are candidates for contracting or merging. Contracting one edge may affect the subset of edges that are legal for contracting at next step. By contracting one edge, we also replace the metrics of the two endpoint nodes with a new smaller metric. We are trying to find an H such that the sum of the metrics of nodes in H is minimal.

Any hint on whether this problem is $NP$-hard($NP$-complete) or not. If so any hint on how to prove it ?

Here are more descriptions: Each node has a 0/1-string label. We define a function to measure the similarity between two labels of the adjacent nodes(i.e. the length of the common prefix of the two labels). At each step only the two adjacent nodes with maximal similarity can be merged (there may be several of them). After we merge the two nodes we label the new node with the common prefix of the original two labels. We also have to preserve the uniqueness of the label. We do no merge if it violates uniqueness of labels. We add up the length of the label of each node in the final graph and try to find the minimum of this number. Or in a more abstract sense, Is labeled graph G contractible (while maintaining our needed invariants e.g. uniqueness of labels) to (given) labeled graph H ?

$\endgroup$
  • $\begingroup$ Can't you represent an ordinary contractibility problem as an instance of your variant simply by setting all metrics to 0 and declare all edges to be candidates? $\endgroup$ – Henning Makholm Jun 30 '12 at 17:39
  • $\begingroup$ The traditional graph contractability problem has no limitation on picking what edge for merging at each step. However in our problem we have different limitations on picking what edge for merging at different steps. This might change the NP-completeness or not. $\endgroup$ – Yinfang Zhuang Jun 30 '12 at 18:41
  • $\begingroup$ Any idea on how to reduce to some well-known np-complete problem ? $\endgroup$ – Yinfang Zhuang Jul 1 '12 at 1:33
  • $\begingroup$ All I can suggest is studying one or more proofs of "traditional graph contractability" to see whether you can modify the methods, or where the methods break down. $\endgroup$ – Gerry Myerson Jul 1 '12 at 4:00
  • 5
    $\begingroup$ Simultaneously posted on cstheory. Please don't do that. $\endgroup$ – JeffE Jul 1 '12 at 20:46