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
vote
1answer
22 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
35 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
15 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
35 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 ...
1
vote
0answers
36 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
37 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
525 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
138 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
275 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
85 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 ...
3
votes
1answer
663 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
85 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
82 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 ...
1
vote
0answers
49 views

finding the minimal subset in bipartite graph violating halls condition

I want to find the minimal subset in bipartite graph violating Hall's condition. More specifically, given a bipartite graph $(S_1,S_2,E)$, finding the minimum cardinality subset of right-vertices $S_2$...
1
vote
1answer
110 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
84 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
81 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
54 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
501 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
120 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
603 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
442 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
190 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
896 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
277 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
231 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
552 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
326 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
462 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
121 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
232 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
130 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
418 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
231 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
64 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
253 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
225 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 ...
3
votes
1answer
263 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
134 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
16k 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 ...
2
votes
0answers
459 views

How can we add back edges in Ford - Fulkerson algorithm?

I was going through the Ford-Fulkerson(FF) algorithm. The given graph is directed and there is an edge from A to B with capacity y. Now sending a flow of x units (x < y) from A to B is equivalent ...
2
votes
0answers
176 views

Min-weight bipartite matching in Christofides' algorithm

Content: The Christofides algorithm finds a minimum spanning tree, then finds all the odd degree vertices, and adds extra edges using a minimum weight bipartite matching on those odd vertices to make ...
3
votes
2answers
1k views

Finding a minimum weight perfect matching in Christofides TSP algorithm

Context: After creating the minimum spanning tree, the next step in Christofides' TSP algorithm is to find all the N vertices with odd degree and find a minimum weight perfect matching for these odd ...
3
votes
2answers
528 views

Maximum bipartite matching when some nodes must be matched

Consider the problem of finding a maximum cardinality bipartite matching under the additional condition that some set $S$ of nodes (all lying on the same side of the bipartition) must be matched. ...
11
votes
0answers
259 views

How fast can we compute the size of maximum matching in an unweighted bipartite graph?

Is there a way to compute the size of a maximum matching in an unweighted bipartite graph more efficiently (e.g. faster) than computing a maximum matching? It is a long shot but it is often an ...
2
votes
1answer
64 views

Computing optimal assignments using little memory

I have two lists where each item in the first list has a rating for each item in the second. I need to determine an optimal matching (or the best x scenarios) where items are matched, but each item ...