Given two graphs $G_{1}(E_{G1},V_{G1})$ and $G_{2}(E_{G2},V_{G2})$, with scalar weights on the vertices, I would like to find a subgraph $H_{1}$ of $G_{1}$ that best matches some subgraph $H_{2}$ of $G_{2}$. However, in most papers I've seen the weights are usually on the edges, $H_{1}$ is pre-specified and the matching being attempted was exact. I would be grateful if somebody could point me in the right direction.

Clarification edit: I'm looking for $H_1(E_{H1},V_{H1})\subset G1(E_{G1},V_{G1})$ and an injective function $f:V_{H1}\rightarrow V_{G2}$ so that $|\{(f(u),f(v))$ $\in$ $E_{G2}$ | $(u,v) \in E_{H1}\}| / |E_{H1}|$ is maximized while the sum of the node weight differences - $\sum_{v \in V_{H1}} |w(f(v))-w(v)|$ is minimized.

  • 3
    $\begingroup$ A couple of clarifying questions: what do you mean by $H_{1}$ matches $H_{2}$? They are isomorphic? Are you given $H_{2}$, or do you only have $G_{1}$ and $G_{2}$ and you have to find both $H_{1}$ and $H_{2}$? $\endgroup$ – Luke Mathieson Jul 10 '13 at 3:34
  • $\begingroup$ Luke, I've edited my question with a more exact formulation of the problem, hope it answers your questions. (I'm not looking for an isomorphism and $H_1$ and $H_2$ are not given. $\endgroup$ – Noam Kremen Jul 10 '13 at 13:56
  • 1
    $\begingroup$ How big would you like $H_{1}$ to be (trivially if size doesn't matter just pick 1 vertex from $G_{1}$ that has the same weight as a vertex in $G_{2}$ and you are done.) Also there is (as I'm sure you know) a trade off between your max-min expressions (unless you have a strong LP duality result like in maxflow-mincut), as you see it is there just a generic real parameter $\lambda\gt0$ and you are trying to maximize (edge condition)$-\lambda$(vertex condition)? $\endgroup$ – Kaya Jul 11 '13 at 16:44
  • $\begingroup$ Kaya, the situation is indeed similar to maximizing $t=EC-\lambda \cdot VC$ . Time complexity permitting , I woould get a list of possible $H_i$ up to a certain minimal t value. $\endgroup$ – Noam Kremen Jul 12 '13 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.