# Questions tagged [bipartite-matching]

The tag has no usage guidance.

172 questions
Filter by
Sorted by
Tagged with
47 views

### Convert a Graph to a Good Graph using Maximum Matching in Bipartite Graphs Algorithm

Consider a graph $G = (V, E)$ where a vertex $v \in V$ is designated as the center if it is connected to every other vertex $u \in V$, such that both $uv$ and $vu$ are present in $E$. A ...
1 vote
35 views

### Finding a matching with a specific weight

Polynomial-time algorithms for finding a maximum-weight matching in a weighted graph are well-known. Suppose I want not the maximum-weight matching, but a matching with a specific weight given as an ...
• 6,070
29 views

### Optimizing Pairings Between Integers and Intervals for Maximal Matching

Consider the scenario where we are given a collection of n integers. These integers are unordered and may include duplicates. Additionally, we have a set of m ranges, each defined by two integers ...
45 views

### Why does Hopcroft-Karp only work on bipartite graphs?

I have a simple question which I cannot answer, and it relates to this question. What I cannot answer is this: Why does a graph with bidirectional edges destroy the "bipartiteness" of the ...
• 155
63 views

### Weighted bipartite maximum cost with a fixed number of vertices

Having a complete bipartite graph with parts $A$ and $B$, which is edge-weighted, is there a way to compute a subgraph with the maximum sum of all weights and: Only a constant number $n$ of vertices ...
• 21
20 views

### flow network, class and classroom matching

Problem: given a set of classes and classrooms, then given a set M of pairs (a,b), which means it is valid assignment from class a to classroom b(ex:(c,2), (c,3), (d,2), means class c can be assigned ...
1 vote
162 views

### Greedy Maximum Bipartite Matching

To find the maximum matching on a bipartite graph, I propose the following greedy algorithm: At each iteration, pick an unmatched vertex with the smallest degree and match it to one of it's neighbours ...
1 vote
113 views

### Expected maximum matching size in a random bipartite graphs

What is the expected maximum matching size of a bipartite graph $(A\cup B, V)$ where $\lvert A\rvert = n$ and $\lvert B\rvert = n$ and the probability of a edge existing between $A$ and $B$ is a fixed ...
81 views

### Dinitz’ algorithm in simple unit-capacity networks

I am studying for an algorithm design course, and can't understand this demonstration about how Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time. This is what is written on the slides ...
1 vote
32 views

### Find an assignment discarding a subset of possible assignments

We have a $N \times N$ cost matrix where the cost denotes the amount incurred for assigning a worker to a task. The number of possible assignments is $N!$. Let us call this set of all possible ...
• 11
41 views

### A bipartite maxiumum matching problem, fitting a ratios vector on the resulting subset

Statement of problem We have two sets of vertices, $V$ and $U$, each of which has a vector of attributes $A$. The set of edges $E$ is defined such that there is an edge $vu\in{E}$ between vertices $v$ ...
• 101
1 vote
40 views

### Schoolclass Optimization Algorithm for finding Stable Matching

I have the task to write a program that puts students in classes and that in the best possible way. We have given the name, the foreign language a student chooses(french or latin), a profile (Music,...
1 vote
81 views

### Bipartite matching with constraints on one part

We have a bipartite graph with parts $A$ and $B$, and it is edge weighted. We have some constraints for part $B$. Each constraint is in this format: Between vertices $b_1$ and $b_2$ both from part $B$,...
1 vote
61 views

### What is the name of this matching problem?

We have a bipartite graph consisting of parts $A$ and $B$. Each vertex $i$ of part $A$ has weight $w_i$ and capacity $c_i$. We say a vertex $i$ in part $A$ is satisfied if at least $c_i$ adjacent ...
136 views

### Budgeted min cost max flow in bipartite where the flows must also be a matching set

I'm trying to find a problem description that is roughly akin to a budgeted min-cost max-weight bipartite matching where the capacities are greater than 1. Imagine a max-flow problem on a graph that ...
57 views

### For a regular bipartite graph with vertices $X\cup Y$, prove that $|S|\leq|n(S)|$ $\forall S\subseteq X$

As the title states, we are given a bipartite undirected graph $G=(X\cup Y,E)$ such that every vertex $v\in V$ satisfies $d(v)=k$ for a constant $k$. The general goal of the proof is to show that ...
• 355
222 views

### A variation of the maximum bipartite matching problem

Given a bipartite simple graph $G=(V,E)$, where $V=A\cup B$ and $A\cap B=\emptyset$, any edge in $E$ connects two vertices in $A$ and $B$, respectively. The maximum bipartite matching problem is to ...
• 25
1 vote
41 views

### Assign items from inventory to people maxmizing the number of satisfied people

We have a set of people, and each person has a list of wished items (not unique, they could want multiple copies of each item). We have an inventory of items that we want to assign to the people. We ...
• 111
1 vote
516 views

### Maximum weighted matching in Bipartite Graph

I was solving a coding question which boiled down to this problem. Given a bipartite graph $G=\{V\cup U,E\}$. There is a positive value given for every node in $U$. Now we have to find the matching ...
1 vote
40 views

• 247
1 vote
62 views

### Using Flow graph to find maximum matching

I recently submitted an answer to the following question (homework in algorithms course): A guy has m shirts, n pants, and p belts. he wants to make the maximum amount of outfits while abiding by ...
• 13
1 vote
347 views

### Max-Min Weighted Matching

The maximum weighted matching problem (https://en.wikipedia.org/wiki/Maximum_weight_matching) finds a matching in a weighted graph that has maximum sum of weights. I was wondering if there are any ...
• 25
1 vote
271 views

### Graph in which greedy algorithm for maximum matching is a 2-approximation

Here is a greedy algorithm for maximum bipartite matching: Iteratively select an edge that is not incident to previously selected edges. This algorithm returns a 2-approximation, and runs in linear ...
• 111
Here is the full version of the problem I'm dealing with. Let $G=(S,T;E)$ be a bipartite graph and let $X$ be one of the two classes of its bipartition (i.e., $X \in \{S,T\}$). For a subset $C \... • 75 1 vote 1 answer 31 views ### Creating an algorithm which utilizes an already known optimal solution to max matching Assume that there is a maximal matching of size k in an bipartite graph, G=(U,V,E). I now want to utilize this maximal matching in order to find a maximal matching in the bipartite graph where we add ... 1 vote 0 answers 72 views ### Hardness result for online matching Currently studying the following paper: "Fair Allocation in Online Markets" - Gollapudi and Panigrahi 2014 In which they present Theorem 2 as a hardness result for online maxmin matchings (... 1 vote 1 answer 799 views ### How to convert Bipartite Perfect Matching to SAT? SAT is$NP$-complete while Bipartite Perfect Matching is in NC under derandomization assumptions. How to convert Bipartite Perfect Matching from balanced bipartites to SAT without Cook-Levin? • 2,901 5 votes 2 answers 329 views ### How to match two point sets to minimize total distance? Let's say we have two sets$X = \{x_1, \ldots, x_n\} \subset \mathbb R^d$,$Y =\{y_1,\ldots, y_n\} \subset \mathbb R^d$, how can we find a permutation$\pi$such that$D = \sum_{i=1}^n d(x_i, y_{\pi(... • 373 0 votes 0 answers 73 views ### Is there a reduction from 2sat to bpm? Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction? • 2,901 1 vote 2 answers 523 views ### Bipartite Graph to solve the wolf river crossing problem I have just started studying about bipartite graphs and there is an example that bipartite graph can be use to solve the wolf, cabbage, and the sheep river crossing problem, as a kid i had fun solving ... • 339 2 votes 0 answers 212 views ### Assignment Problem with Minimum and Maximum constraints [duplicate] I have the following problem: In a school, there are n students and m clubs, with n > m. Each student needs to be assigned a club. The students have preferences, (say top 3 or top 5) of the clubs ... • 285 1 vote 0 answers 61 views ### Algorithms for alignment of posets I have been looking for a while but I cannot find an algorithm for a particular generalisation of sequence alignment. I have two posets(A, <)$and$(B, <)$and a similarity score$s(a, b)$for ... • 111 0 votes 1 answer 88 views ### How to simulate online matching algorithms (implementation) I was reading about online algorithms and bipartite matching. I found an implementation that works fine on several websites (like geeksforgeeks). For the online version, I found this paper https://... 1 vote 0 answers 44 views ### Find approximate 'best' matching pairs by calculating the fewest possible weights My specific problem is as follows: Given two list of texts (in the order of 5 to 50 items) Find best matching pairs with their corresponding matching score (weight) Where each item can only be ... • 111 1 vote 1 answer 26 views ### Predicate variant of Assignment Problem Given two equally sized sets,$P$of Boolean predicates and$E$, I want to decide if there exists a bijective function$f: P \rightarrow E, such that \begin{align} \forall p \in P \; p(f(p)) \end{... • 113 0 votes 1 answer 74 views ### why does relabel take O(VE) time total for unit capacity flow networks? It is well known that for arbitrary flow networks, Goldberg's push-relabel algorithm takesO(V^2E)$. Part of that comes from$O(V^2E)$non-saturating pushes. Another part comes from$O(V)$... • 858 1 vote 1 answer 120 views ### Flow graph with non zero lower bound or 0 capacity I am afraid the question title might not be sufficiently accurate but I could not come up with something more accurate Here is the problem Given 'n' machines Each machine has a set of capabilities ... 2 votes 0 answers 64 views ### Tight sets w.r.t. Hall's condition Consider a bipartite graph G=(U+V,E) and suppose |U|=|V| and that G has a perfect matching. Therefore by P. Hall's condition, for every subsets A of U, the neighborhood N(A) of A has size at least |A|.... • 121 2 votes 1 answer 263 views ### Min weighted edge cover: don't follow proof in Schrijver I'm reading section 19.3 of Combinatorial Optimization by Schrijver where he details an algorithm for finding the min-weight edge cover. His method works for general graphs, but I'm particularly ... • 377 2 votes 1 answer 364 views ### Bipartite maximum matching with added constraints Suppose you have two lists as follows List$A$=$(a_1, a_2, ..., a_m)$List$B$=$(b_1, b_2, ..., b_n)$Each element in list$A$can be paired with many or no elements in list$B$. I have a function ... • 121 3 votes 1 answer 183 views ### Minimize range of distances between two sets of points I have two sets of n points each in 2D Cartesian coordinates. I want to find a one-to-one pairing between the points in sets A ... • 131 4 votes 1 answer 364 views ### Find a maximum matching that saturates a given set of vertices In an unweighted bipartite graph$G = (X + Y,E)$, we would like to find a maximum matching, but among all those maximum matchings, we would like to find one that saturates a given subset$X_0\subseteq ...
Consider a bipartite Garph $G=(L \cup R, E)$. Naturally, a b-Matching problem is to find a set of edges $M \subset E$, such that each node in $L$ and $R$ are adjuscent to maximum $b$ neighbors, and a ...