Skip to main content

Questions tagged [bipartite-matching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
Stephen Stone's user avatar
1 vote
1 answer
36 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 ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
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 ...
jack norton's user avatar
2 votes
1 answer
51 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 ...
Joff's user avatar
  • 155
2 votes
1 answer
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 ...
Lozan's user avatar
  • 21
0 votes
0 answers
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 ...
Joseph Ritcher's user avatar
1 vote
1 answer
170 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 ...
eeeeellllll's user avatar
1 vote
1 answer
114 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 ...
Anonymous's user avatar
2 votes
1 answer
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 ...
Placido Pellegriti's user avatar
1 vote
0 answers
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 ...
akhil's user avatar
  • 11
0 votes
1 answer
42 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$ ...
RealSkeptic's user avatar
1 vote
1 answer
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,...
Hagenbeck's user avatar
1 vote
1 answer
83 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$,...
Soroush Vahidi's user avatar
1 vote
0 answers
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 ...
Soroush Vahidi's user avatar
0 votes
0 answers
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 ...
scubadude22's user avatar
2 votes
1 answer
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 ...
Aishgadol's user avatar
  • 355
0 votes
1 answer
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 ...
Soha's user avatar
  • 25
1 vote
1 answer
42 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 ...
mdatsev's user avatar
  • 111
1 vote
1 answer
530 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 ...
aquib nawaz's user avatar
1 vote
1 answer
40 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 \...
3nondatur's user avatar
  • 457
1 vote
2 answers
211 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 ...
Sam's user avatar
  • 11
0 votes
1 answer
45 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 ...
Keio203's user avatar
  • 257
2 votes
2 answers
86 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 ...
JMenezes's user avatar
  • 135
1 vote
1 answer
67 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 ...
zdm's user avatar
  • 1,046
2 votes
0 answers
46 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 ...
NiRvanA's user avatar
  • 159
2 votes
1 answer
174 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 ...
Kombajn's user avatar
  • 123
1 vote
1 answer
70 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 $...
Reinderien's user avatar
1 vote
1 answer
63 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 ...
NoamV's user avatar
  • 13
1 vote
1 answer
353 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 ...
Nick's user avatar
  • 25
1 vote
0 answers
272 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 ...
shima's user avatar
  • 111
5 votes
1 answer
84 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 \...
0410's user avatar
  • 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 ...
Andreas Andersson's user avatar
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 (...
user143196's user avatar
1 vote
1 answer
803 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?
Turbo's user avatar
  • 2,901
5 votes
2 answers
331 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(...
flawr's user avatar
  • 373
0 votes
0 answers
74 views

Is there a reduction from 2sat to bpm?

Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
Turbo's user avatar
  • 2,901
1 vote
2 answers
527 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 ...
kiv's user avatar
  • 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 ...
devam_04's user avatar
  • 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 ...
Epimetheus's user avatar
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://...
aNormalPerson's user avatar
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 ...
de1's user avatar
  • 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{...
Jonas Nyrup's user avatar
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 takes $O(V^2E)$. Part of that comes from $O(V^2E)$ non-saturating pushes. Another part comes from $O(V)$ ...
xdavidliu's user avatar
  • 858
1 vote
1 answer
122 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 ...
Peter Coppens's user avatar
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|....
giuper's user avatar
  • 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 ...
Rohit Pandey's user avatar
2 votes
1 answer
366 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 ...
fardeem's user avatar
  • 121
3 votes
1 answer
185 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 ...
apilat's user avatar
  • 131
4 votes
1 answer
365 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 ...
Erel Segal-Halevi's user avatar
2 votes
1 answer
1k 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 ...
mcqueenvh's user avatar