Subgraph isomorphism on star multi-graphs with labelled edges 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?
After you fix the star centers, your problem is simply bipartite matching.