Questions tagged [bipartite-matching]
The bipartite-matching tag has no usage guidance.
158
questions
0
votes
0
answers
53
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 ...
2
votes
1
answer
49
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 ...
- 316
0
votes
1
answer
104
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 ...
- 15
1
vote
1
answer
35
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
1
answer
136
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 ...
- 11
1
vote
1
answer
36
views
How to argue that an $A$-covering matching exists in this bipartite graph?
In lecture the following was mentioned in the context of matchings in bipartite graphs:
Let $U$ be a finite set and let $\mathcal{S}$ be a family of subsets of $U$.
For $u \in U$ let $r(u) := \lvert \...
- 457
1
vote
2
answers
93
views
Matching students with companies based on their preference
I have a list of companies with n timeslots (number of slots may vary from company to company) and a list of students. Each student made a list of their top 3 companies they would like to talk to.
Is ...
- 11
0
votes
1
answer
30
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 ...
- 257
2
votes
2
answers
57
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 ...
- 133
1
vote
1
answer
46
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,026
2
votes
0
answers
36
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 ...
- 159
2
votes
1
answer
113
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 ...
- 123
1
vote
1
answer
52
views
Optimal prune of a mutually-exclusive bipartite graph
I start with a complete edge-weighted unbalanced bipartite graph.
For a known, fixed $n$ on the order of 1000:
$$0 \lt n, n \in I$$
Left and right cardinalities might not be equal; for sides $U$ and $...
- 237
1
vote
1
answer
45
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
1
answer
96
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
0
answers
175
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
5
votes
1
answer
81
views
The maximum matching of a bipartite graph $(S, T)$ is $|X|+\min\limits_{A \subseteq X} (\min\{0, |N_G(A)|-|A|\}$, where $X \in \{S, T\}$?
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
29
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
71
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 (...
- 11
1
vote
1
answer
584
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,862
5
votes
2
answers
183
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
49
views
Is there a reduction from 2sat to bpm?
Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
- 2,862
1
vote
2
answers
328
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
142
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
58
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
65
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
42
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
25
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
61
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
1
answer
82
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
54
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
195
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 ...
- 295
1
vote
1
answer
253
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
3
votes
1
answer
156
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
233
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 ...
- 5,844
2
votes
1
answer
635
views
Is there such a problem as b-Matching with different b values?
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 ...
- 53
1
vote
2
answers
142
views
Bipartite graphs with min weights
I have a full bipartite graph with node sets $A=\{a_1,a_2,\ldots,a_n\}$ and $B=\{b_1,b_2,\ldots,b_n\}$. Each node has a weight, $v_i$ for $a_i$ and $w_i$ for $b_i$. Each node $a_i$ is connected to ...
- 940
4
votes
1
answer
135
views
Efficient algorithm to map two differently-sized sets of numbers as closely as possible?
The problem
I have two sets of numbers and need to find a mapping between those two sets, so that the total distance between two mapped numbers is as small as possible. Two numbers must not be mapped ...
- 141
0
votes
1
answer
48
views
Problem with understanding Multi-party security circuit for secure stable matching
I am reading the following paper:
MPCircuits: Optimized Circuit Generation for Secure Multi-Party Computation
Paper Link
I have following question:
We have two groups shown in the circuit. Why we ...
- 251
0
votes
1
answer
61
views
Bipartite Graph in a Digraph
How do you find a sub-digraph in a digraph such that the in degree and out degree of each vertex is 1. My professor told in the class that an algorithm can be build for it using bipartite matching but ...
- 49
5
votes
1
answer
183
views
Saturated sets in bipartite graph
Let $G=(X\cup Y, E)$ be an unweighted bipartite graph. We are given that for every $W\subseteq X$ it holds that $|W|\leq |N(W)|$, where $N(W)$ is the neighborhod of $W$ in $Y$ (aka Hall's marriage ...
- 229
2
votes
0
answers
349
views
What is the time complexity of the Edmonds-Karp algorithm for finding a maximum cardinality matching in bipartite graphs?
What is the time complexity of the Edmonds-Karp algorithm (not the Hopcroft-Karp algorithm) for finding a maximum cardinality matching in bipartite graphs? Is it still $O(|V||E|^2)$, or it has a ...
0
votes
0
answers
62
views
Maximum Matching for Line Graphs
I tried to study the maximum matching for a line-graph , i.e , $L(G)$ of a graph , $G(V,E)$ , from here :
https://www.sciencedirect.com/science/article/pii/S0012365X97001039
But could not understand ...
0
votes
0
answers
68
views
How to solve this problem using the Maximum matching algorithm for general graph?
For any general graph G(V,E) , the maximum matching can be calculated in O(√V.|E|) time using the following algorithm :
https://www.researchgate.net/publication/...
0
votes
1
answer
110
views
Perfect Matching in Bipartite Graph with mutually exclusive edges
Problem
I would to solve Perfect Matching in Bipartite Graph Problem where some edges are mutually exclusive.
Example
Left vertices: $a,b,c$
Right vertices: $x,y,z$
Edges: $(a,x),(a,y),(b,z),(c,y)...
- 103
4
votes
1
answer
340
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
2
votes
1
answer
223
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,358
7
votes
1
answer
263
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 ...
- 73
3
votes
1
answer
174
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$. ...
- 61
1
vote
1
answer
748
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:
...
user106782