2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Apr 20, 2022 at 4:37

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ True, but is there any way to do it without enumation. For example if I have 50 individuals in each group? My example, was short just in a effort to be didatic $\endgroup$
    – JMenezes
    Apr 20, 2022 at 11:14
1
$\begingroup$

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.

See also the Wikipedia articles on bipartite graph realization and on the Gale-Ryser theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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