I am looking for a heuristic for a graph matching problem as follows.
Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than that of $A$.
Each node and edge in two graphs has weight. The task is to match graph $A$ to graph $B$, i.e., find a set of nodes and links in $B$ to map each node and link of $A$, such as the host node/link in $B$ has larger weight than the corresponding node/link of $A$.
The following figure illustrates two possible cases (or solution) of mapping (matching):
Case 1: One-to-one mapping: Each node or edge of $A$ needs only one node or link of $B$ to map. Here the nodes $a_1, a_2, a_3$ are mapped on to $b_1, b_2, b_3$, and the edges $a_1a_2, a_2a_3$ are mapped onto $b_1b_2$ and $b_2b_3$ respectively.
- Constraints are satisfied: For nodes: $b_1 > a_1$, $b_2 > a_2$, $b_3 > a_3$. For edges: $b_1b_2 > a_1a_2$ and $b_2b_3 > a_2a_3$.
Case 2: One-to-many mapping: One needs more than 1 node/edge of $B$ to host a node/edge of $A$. In the example, $a_1$ is mapped on to $b_1$ and $b_4$, $a_2, a_3$ are mapped onto $b_2, b_3$. For the edges: $a_1a_2$ is mapped onto $b_1b_2$ and $b_4b_2$, and $a_2a_3$ is mapped onto $b_2b_3$.
- Constraints are satisfied: For nodes: $b_1 + b_4 = 11 > a_1$, $b_2 > a_2$, $b_3 > a_3$. For edges: $b_1b_2 + b_4b_2 = 8 > a_1a_2$ and $b_2b_3 > a_2a_3$.
Heuristics for Case 1 have been well studied, e.g., using eigendecomposition to solve the Weighted Graph Matching Problem (WGMP). Nevertheless, I could not find an appropriate algorithm to find a solution as in Case 2. Any suggestions?