4
$\begingroup$

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

pattern graph

and the target

enter image description here

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?

$\endgroup$
  • 1
    $\begingroup$ Can you define star-shaped multigraph? $\endgroup$ – Yuval Filmus Aug 24 '18 at 5:04
  • $\begingroup$ Thanks for asking, I've added an example to illustrate the problem. What I mean is a star graph where the edges in the star graph can be multi-edges with potentially different labels. $\endgroup$ – Moormanly Aug 24 '18 at 6:59
0
$\begingroup$

After you fix the star centers, your problem is simply bipartite matching.

$\endgroup$
  • $\begingroup$ Thanks for your answer, I will read up on bipartite matching. Do you have any references you would recommend? $\endgroup$ – Moormanly Aug 25 '18 at 11:04
  • $\begingroup$ Did some reading, thanks for providing the search terms. My problem is exactly maximum bipartite matching. $\endgroup$ – Moormanly Aug 25 '18 at 15:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.