# Matching problem in bipartite network with more than one edge per vertex

I'm interested to know if there is an algorithm to find possible solutions for the matching problem, in a bipartite network where each vertex have maximum number of connections greater than one. For reference the original matching problem only requires that each vertex only have one edge.

More specifically, imagine that i have two groups of individuals $$X = \{a,b,c,d\}$$ and $$Y= \{e,f,g,h\}$$. I want to generate random solutions such that every element of $$X$$ is connected to at least 1 of $$Y$$ but to no more than 3, and that every element of $$Y$$ is also connected to either 1,2 or 3 elements in $$X$$.

Any ideas how to implement that, or, if there is a specific name for this kind of problem? That makes it more likely to find a function in R that solves it.

• What does "number of allowed vertex per edge" mean? Do you want to find a possible solution or a random solution? If you want a random solution, what distribution on solutions are you looking for? Please edit the question.
– D.W.
Commented Apr 20, 2022 at 4:37

With only two groups of 4 individuals, there are at most $$2^{4 \times 4} = 65536$$ different candidate solutions, so it is trivial to enumerate all possible solutions and check each one to see whether it meets your conditions.
When you generate random instances, you need to consider if you have a specific probability distribution in mind. You could suppose that the degree of each vertex is chosen uniformly at random from $$\{1,2,3\}$$.
If $$a_1,a_2\ldots,a_n$$ and $$b_1,b_2,\ldots,b_n$$ are the left and right vertices of the bipartite graph, then choose each $$a_i$$ and $$b_j$$ at random from $$\{1,2,3\}$$. The degree sequence $$(a,b)$$ is realizable (i.e. there exists a bipartite graph having $$(a,b)$$ as its degree sequence) if the Gale-Ryser theorem is satisfied, which you can check. This theorem would not be satisfied for all random instances, but it does give a condition that is both necessary and sufficient for a degree sequence to be realizable. Then, you can generate a bipartite graph with this degree sequence; see Exercise 1.4.32 of [D. West, Introduction to Graph Theory, 2e]. An issue is perhaps most degree sequences might not be realizable.