My approach to the problem has been to reformulate it into something more recognizable, but I don't know the best way to solve the reformulated problems either. I list the original problem, an example, and two reformulations below. The second reformulation is equivalent to an unbalanced assignment problem with a binary cost matrix.
Original Formulation
I have two star multigraphs: A small pattern, and a large target. The graphs may have multiple edges between a single pair of nodes. The edges of each graph have labels from some small set of labels. I am looking for the most efficient algorithm to check if there exists a subgraph of the target which is isomorphic to the pattern.
Example
Consider the pattern
and the target
where edge colors represent labels. There is a subgraph of the target consisting of the nodes 1, 2, 3, and 5 (and some edges that I haven't given names) which is isomorphic to the pattern graph. Note that the subgraph need not be a node-induced subgraph, and is not in this case.
Reformulation 1
Enumerate the neighbors of the center of each graph: $1, 2, \dots n_{\mathrm{pattern}}$ and $1, 2, \dots n_{\mathrm{target}}$. Define $A_{i,j}=1$ if node $i$ in the target has at least as many edges of each type to the target's center as node $j$ in the pattern has to the pattern's center. If the constraint is not met, then $A_{i,j}=0$. The problem becomes: Given a binary matrix $\mathbf{A}$ with more rows than columns, does there exist a permutation of the rows such that the main diagonal is all ones?
Reformulation 2
You are given $n_{\mathrm{target}}$ workers to perform $n_{\mathrm{pattern}}$ tasks, where each worker is competent in only a subset of the tasks. Does there exist an assignment of workers to tasks such that each task has at least one competent worker assigned?
