# Questions tagged [bipartite-matching]

The tag has no usage guidance.

151 questions
Filter by
Sorted by
Tagged with
24 views

### Proving that this matching is stable

Consider the stable marriage problem with $n$ men and $n$ women. Let $A$ and $B$ be two stable matchings, and suppose that we form a new matching $C$ by assigning to each men his favorite partner ...
• 245
35 views

### Matching problem in bipartite network with more than one edge per vertex

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 ...
• 123
1 vote
42 views

### Find a perfect matching with weights as close as possible to each other

Given a set of jobs $J$ and a set of machines $M$, where the link between machine $i\in M$ and job $j\in J$ has a positive weight $w_{ij}$. The problem is to select a perfect matching between the jobs ...
• 1,016
29 views

### Proving existence of sinkless orientation on graph with minimum degree 2

I am given a graph of minimum degree at least 2 (not necessairly regular). I want to prove that there is a way to orient the edges of G such that each node of G has at least one out-going edge. As a ...
• 149
58 views

### confusion about Hopcroft-Karp time complexity analysis

From Wikipedia: "Each phase increases the length of the shortest augmenting path by at least one: the phase finds a maximal set of augmenting paths of the given length, so any remaining ...
• 23
1 vote
33 views

• 75
1 vote
24 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 ...
12 views

### Find a matching of a bipartite graph that uses all vertices in the left set

I have a bipartite graph already divided into a left and right set, and I would like to find a matching that uses all of the vertices in the left set. To phrase this problem less abstractly, I have a ...
1 vote
70 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
138 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,824
103 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
40 views

### Is there a reduction from 2sat to bpm?

Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
• 2,824
1 vote
207 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
106 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 ...
• 275
1 vote
51 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
49 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
37 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
23 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
44 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 takes $O(V^2E)$. Part of that comes from $O(V^2E)$ non-saturating pushes. Another part comes from $O(V)$ ...
• 818
1 vote
63 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 ...
34 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
151 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 ...
• 307
1 vote
156 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 ...
• 111
74 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
147 views

• 103
312 views

### Maximum matching in a bipartite graph

Given a bipartite graph $G=(V_1 \cup V_2, E)$ and a set $V' \in (V_1 \cup V_2)$. What is the complexity of finding a maximum matching in $G$ that uses only $x$ vertices from $V'$?
• 385
204 views

### Hardness of a scheduling/assignment problem

I am trying to prove the hardness of the following problem. This problem is from google hashcode, qualification-round, 2020. Hier is a brief description of the problem. Given a list or libraries and ...
• 4,093
247 views

### Winning strategy for a given game on graphs

The game goes as follows. Two players are playing a game, player 1 and player 2, in which the first player starts by naming a hero $h_1$, then player 2 responds with a villain $v_1$ who has played in ...
167 views

### Assignment Problem -- finding the $k$ agents with the best assignment

I have a question that I have been thinking about. Suppose we have $n$ agents, $m$ tasks, a cost matrix with $M_{ij}$ being the cost of agent $i$ performing task $j$, and are given a value $k \leq n$. ...
1 vote
642 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: ... 56 views

### Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?

Consider a set $P$ of $N$ intervals $\{I_i = (l_i, r_i)\}$ partially ordered according the standard interval order: $I_i < I_j$ iff $r_i \le l_j$. I want to find a minimum cardinality partition of ...
• 227
364 views

### An example where the algorithm of Hopcroft and Karp performs poorly?

I have been trying to construct an example, where Hopcroft and Karp's algorithm for the maximum matching problem performs poorly (say at least $\Omega(\log n)$ rounds). However, all the examples I ...
• 4,093
500 views

### Bipartite graph minimal amount of vertices required

I have a bipartite graph made of two sets (SET 1 and SET 2) and I want to determine how many vertices from the ...
• 23