# Questions tagged [bipartite-matching]

The tag has no usage guidance.

16 questions
Filter by
Sorted by
Tagged with
1k views

### Finding a subset in bipartite graph violating Hall's condition

We are given a bipartite graph of $n \leq 200$ vertices in both the first and the second partite set. Let $U$ be some set of vertices in the first set, and $V$ those vertices from the second that are ...
9k views

### The stable marriage algorithm with asymmetric arrays

I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices. ...
6k views

### How to find the maximum independent set of a directed graph?

I'm trying to solve this problem. Problem: Given $n$ positive integers, your task is to select a maximum number of integers so that there are no two numbers $a, b$ in which $a$ is divisible by $b$...
2k views

### Number of ways to fill a 2xN grid with M colors

This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri. In short, the question asked to find the number of ways to fill a $2\times N$ grid with $M$ colors such that no two ...
4k views

### Stable marriage problem with only one side having preferences [duplicate]

I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and ...
1 vote
492 views

### Weighted Matching with multiple assignments and min assignments

I need to do a weighted matching between two sets (say students and professors). The set of students is much larger than set of professors. So multiple students can be matched to professors. However, ...
533 views

### Given 2 sets of n points: minimize sum of traveled distances

I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean ...
535 views

### Decomposing a bipartite graph of maximal degree d to d matchings

I have tried for the last few days to prove that any bipartite graph of maximal degree d may be broken into (at most) d matchings. My main approach is to prove this inductively over the maximal ...
Given a bipartite graph $G(X+Y,E)$, how can I find a non-empty subset $Y'\subseteq Y$, such that $|N(Y')| \leq |Y'|$ (where $N$ is the set of neighbors)? If $|Y|\geq |X|$ then the problem is easy - $... 4 votes 1 answer 2k views ### Changing preference in Gale-Shapley algorithm? Suppose, in the context of the classic marriage problem, two equal size groups of$n$men and$n$women are being matched, with the GS algorithm. If a man were to switch the order of a pair of women, ... 4 votes 1 answer 435 views ### Assignment problem with no cost I have a problem that I was able to conceptualize as following: Problem We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination of ... 3 votes 1 answer 2k views ### Existence of bipartite perfect matching Let$B = G(L, R, E)$be a bipartite graph. I want to find out whether this graph has a perfect matching. One way to test whether this graph has a perfect matching is Hall's Marriage Theorem, but it is ... 2 votes 1 answer 1k views ### Polynomial time solution for bipartite matching Inspired by this StackOverflow question, I am wondering if there is an efficient algorithm for the following problem: Assume$n$items and$n$boxes, with all boxes numbered numerically and all ... 2 votes 1 answer 1k views ### Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut (... 1 vote 1 answer 745 views ### How to find maximum matching edges in undirected tree Let$B$be an undirected tree with$|V|$nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime$\mathcal{O}(|V|)\$. My approach: ... 