Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [bipartite-matching]

The tag has no usage guidance.

-1
votes
0answers
28 views

Real estate maximum matching algorithm

I’m working in real estate company and when we launch a new project we receive thousands of customers everyone with a list of several choices of units ordered by priority 1st and 2nd and 3rd. Clients ...
0
votes
1answer
18 views

minimum cardinality maximal matching of graph

How to find minimum cardinality maximal matching? I tried that pick a edge from highest degree vertex remove other edges from same vertex and so on.
1
vote
1answer
28 views

Matching schedules between users and providers

I have a problem I've been dealing for the past few days, and I'm pretty stuck. Each user has a schedule for a given week, such as ...
4
votes
1answer
95 views

Finding a subset with few neighbors

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 - $...
2
votes
1answer
24 views

Using LP to prove the max matching - min cover theorem

Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following ...
1
vote
2answers
47 views

Either find a perfect matching, or return a witness that none exist [duplicate]

I am looking for a polynomial-time algorithm that takes as input a bipartite graph $(X\cup Y, E)$, and returns one of two options: If a perfect matching exists, it returns the matching; Otherwise, it ...
1
vote
1answer
27 views

Multiple rounds of bipartite matching problem

I have a set of investors (say n), and a set of startups (say m). At the start, I have all the investors say either yes or no to the startup (which corresponds to whether they want to interact with ...
0
votes
1answer
36 views

More efficient maximum bipartite matching

I've been looking into weighted matching in bipartite graphs and am currently looking at maximum matchings in weighted bipartite graphs. As I've been reading and poking around at different books and ...
1
vote
0answers
21 views

Hungarian algorithm to search over all matching?

I am working on the following problem- "Finding the matching among all possible matching such that the sum of edge weight is minimum in the matching." Please note that I like to search over all ...
2
votes
0answers
36 views

Find the set of edges in a bipartite graph such that the sum of edge weights is maximum satisfying some constraints

Let $G$ be a bipartite graph with sides $L$ and $R.$ Let $w_{lr}$ be the edge weight of an edge from $l \in L$ to $r \in R.$ Let $x_r$ be the node weight of the node $r \in R.$ Let $E$ denote the set ...
3
votes
1answer
25 views

Determine whether two collections of items can be paired

Given collections I (items) and S (slots), where I >= S. And a pairing function that ...
2
votes
0answers
41 views

How can I find matchings in a Bipartite graph beginning with specific vertices?

Context: I'm modelling kidney exchanges through directed acyclic graphs. I convert these to Bipartite graphs (by splitting each node into a donor and receiver, and the edge from the original graph ...
2
votes
2answers
34 views

Can a perfect matching always be found by a picking sequence?

There are $n$ people and $n$ items. For each person, there is a set of items he likes. Our goal is to give to each person a single item that he likes, i.e, find a perfect matching in the preference ...
1
vote
0answers
39 views

Finding maximum bipartite matching

I read an article https://www.geeksforgeeks.org/maximum-bipartite-matching/ to solve the maximum bipartite problem. In this article, two solutions are given. In the first solution, they have ...
1
vote
1answer
598 views

Perfect matching in a bipartite regular graph in linear time

Given a $G=(V,E)$ bipartite, undirected, 4-regular graph, I would like to find a perfect matching in linear time. It is easy to show that there is a perfect matching for the graph, by using flow and ...
2
votes
1answer
212 views

Bipartite Perfect Matching “Assignment Problem” - finding an assignment of a particular weight

The assignment problem is to find the minimum weight perfect matching in a weighted bipartite graph. This problem can be solved using the Hungarian algorithm in polynomial time. It is also possible to ...
3
votes
1answer
377 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, ...
6
votes
0answers
93 views

Complexity of removing edges to eliminate a perfect matching

Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this ...
4
votes
1answer
732 views

Konig's Theorem for Min Weight Vertex Cover?

Koning's theorem states that the cardinality of the maximum matching in a bipartite graph is equal to the size of its minimum vertex cover. Wikipedia states that there is an equivalent version of the ...
1
vote
1answer
87 views

I have n boys and n girls. I need to pair as much of them as possible for a dance in O(nlogn). Reduce this to a standard problem?

There are n girls and n boys. Each girl i has an objective attractiveness constant Pi (a natural number). The bigger the number, the more attractive. Each boy has a range in which he is comfortable ...
1
vote
1answer
57 views

Understanding characterizations of Matching on Graphs

I am studying Matching Theory on Graphs and I am wondering if I understand the characterization of the problems right. Definition: Let $G = (V, E)$ a graph. A set $M \subseteq E$ is called a matching ...
2
votes
1answer
84 views

How to find n-1 complete matches for bipartite graphs that are related (speed-date)?

How can one assign n people pairwise to n-1 tables, in a speed-date fashion, such that no two persons meet twice and each person is at each table exactly once? Does this problem have a name? The ...
7
votes
2answers
170 views

Find a minimum-cardinality Hall-violator

Given a bipartite graph $(X,Y,E)$, in which there is no perfect matching, I want to find a smallest subset that violates Hall's condition, i.e., a minimum-cardinality set $S \subseteq X$ for which $|...
1
vote
1answer
146 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, ...
2
votes
1answer
90 views

Variant of bipartite matching, with real capacities from source and to sink, all others unlimited

I've got a variant of bipartite graph matching and I can't find any literature about it. We have bipartite graph with real capacity edges from source to left vertices (the sum of which is 1), real ...
1
vote
1answer
103 views

Is Gale Shapley globally optimal?

Let us have a set of N men and N women, and we have two matrices of affinities $M$ and $W$ such that $M(i,j)$ is the affinity of the ith man towards the jth woman and $W(i,j)$ is the affinity of the ...
3
votes
0answers
55 views

Find If a node exists in all maximum bipartite matchings

Given a bipartite graph, I need to find for each node, If this node exists in all the possible maximum matchings of the given graph or not. Note that there can be multiple maximum matchings of a ...
3
votes
1answer
553 views

What is the best algorithm to match a student's schedule with a tutor's schedule?

I am building an application (RoR framework) that can help to match a tutor and a student based on their subjects, budgets, locations and freetime. I have done the first three parts(subjects, budgets, ...
4
votes
1answer
124 views

3✕n chessboard with holes - maximum number of knights not attacking each other

I'm trying to to create an algorithm (working in polynomial time) to solve the following problem: What maximum number of knights that any two of them don't attack each other can be placed on a 3✕n ...
0
votes
0answers
618 views

Network Flow - Bipartite Matching: Doctors Without Weekends Problem

Problem You've periodically helped the medical consulting firm Doctors Without Weekends on various hospital scheduling issues, and they've just come to you with a new problem. For each of the next n ...
0
votes
1answer
456 views

maximum matching in a bipartite graph for solving a chess rook maximization problem

There's an n x n chessboard where some cells are instead holes. I want to have as many rooks as possible in a way that the rooks won't be able to capture each other....
7
votes
1answer
194 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 ...
9
votes
2answers
948 views

Reducing max flow to bipartite matching?

There's a famous and elegant reduction from the maximum bipartite matching problem to the max-flow problem: we create a network with a source node $s$, a terminal node $t$, and one node for each item ...
0
votes
1answer
290 views

Find perfect matching faster than MCM, in graph that has perfect matching?

Given an unweighted bipartite graph which has a perfect matching, is there an algorithm for finding a perfect matching in the graph that is faster than the best known algorithm for finding a maximum ...
4
votes
2answers
232 views

Auction where each bidder bids on a bundle of items

Is there some optimal solution in an auction where each bidder bids on a bundle of items?
5
votes
1answer
566 views

Hungarian Algorithm - Arbitrary Assignments

I've looked at several explanations of the Hungarian Algorithm for solving the Assignment Problem and the vast majority of these cover only very simplistic cases. The most understandable explanation ...
2
votes
1answer
362 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 ...
5
votes
0answers
481 views

Faster maximum weight matching algorithm in bipartite graph

I need to do a maximum weight matching in bipartite graphs rather than maximum weight perfect matching (which means that there is no need to match all the nodes). The nodes each side are both (at ...
1
vote
1answer
125 views

Problems that are easy on bipartite but hard on general graphs

Are there any problems that are easy for bipartite graphs, but hard for general graphs? I am asking because some classical problems are formulated in reference to people looking for a spouse, such as ...
1
vote
1answer
239 views

Why is bipartite graph matching hard?

I am reading on how solving maximum flow (Ford-Fulkerson) can be also used to solve unweighted bipartite graph matching problem. I think I don't understand the essence of this problem, because to me ...
0
votes
2answers
142 views

Minimizing the overall cost over groups

I am trying to solve the problem of minimizing the overall cost over several groups. The schema of the data goes something like this: ...
0
votes
1answer
453 views

Multiple matching in Maximum Flow problem?

I'm sorry if this has already been asked before, but I couldn't find any similar questions. The situation is as such: Assume there are x restaurants, each with a capacity q, and y people, each of ...
3
votes
0answers
153 views

Online bipartite edge-cover problem with requirements

I have $N$ nodes $v_1,\ldots,v_N$ in one partition $X$ and $M \leq N$ nodes $u_1,\ldots,u_M$ in a different partition $Y$. I want to connect nodes in $X$ to nodes in $Y$ with edges under the following ...
1
vote
1answer
246 views

A condition ensuring that a bipartite graph have a perfect matching

There is a bipartite graph $G=(A,B,E)$ such that for every edge $(a,b)$ (where $a$ comes from $A$ and $b$ from $B$), $\deg(a) \geq \deg(b)$, and additionally $\deg(a) \geq 1$ for all $a \in A$. From ...
3
votes
0answers
65 views

Complexity class of a counting problem

Consider the following inequalities: $\sum_j a_{ij}x_{ij}=1 \;\;\; i=1,...,n$ $\sum_i a_{ij}x_{ij} \le y_i \;\;\; j=1,...,n$ $x_{ij} \ge 0 \;\;\; i,j=1,...,n$ $y_i \in \{0,1,2\} \,\,\,\, i=1,...,...
1
vote
1answer
265 views

Match students and teachers based on ranking

I have a similar question to that of Stable Marriage Problem. This is the criteria1) 1 Student must have 1 Teacher only.2) 1 Teacher ideally should have 3-4 Students. The spreadsheet is done using ...
2
votes
2answers
229 views

Is there a name/algorithm for this problem related to set cover and CSP?

Our college would like to determine if a transcript contains classes that satisfy every general education requirement. What makes this nontrivial is that while a single class may in theory satisfy ...
4
votes
1answer
291 views

Maximum bipartite matching with extra reward for covering certain sets

Consider the following variation of Bipartite Maximum Matching. As usual, we have a bipartite graph $G$. In addition, there is an additional collection of sets $S_1,S_2,\dots,S_k$, with each set $...
4
votes
1answer
137 views

Why is bipartite perfect matching a special case of clique problem?

In Lovász writes [1] : bipartite graph has a perfect matching, which is a special case of the clique problem Why is bipartite perfect matching a special case of clique problem? The Work of A.A. ...
3
votes
1answer
17k views

Perfect matching in a graph and complete matching in bipartite graph

When I google for complete matching, first link points to perfect matching on wolfram. It defines perfect matching as follows: A perfect matching of a graph is a matching (i.e., an independent ...