Skip to main content

Questions tagged [bipartite-matching]

The tag has no usage guidance.

32 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5 votes
0 answers
781 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 ...
Kaho Chan's user avatar
  • 161
3 votes
0 answers
382 views

What is the exact time complexity of randomized Kuhn's algorithm?

Please, read the whole question before answering, the exact details of the implementation are important. Suppose that you want to find largest cardinality bipartite matching in bipartite graph with $...
Kaban-5's user avatar
  • 519
3 votes
0 answers
147 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 ...
Gena's user avatar
  • 151
3 votes
0 answers
163 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 ...
utdiscant's user avatar
  • 661
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
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
0 answers
457 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 ...
Mehrad Zamani's user avatar
2 votes
0 answers
63 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 ...
sankha's user avatar
  • 21
2 votes
0 answers
81 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,...,...
Yang Wang's user avatar
2 votes
0 answers
780 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 ...
harun_a's user avatar
  • 135
2 votes
0 answers
343 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 ...
yjc's user avatar
  • 171
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
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
1 vote
0 answers
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 ...
shima's user avatar
  • 111
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
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
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
0 answers
56 views

bipartite d regular expender explicit construction

I am looking for an explicit (and simple) construction of a d regular bi bipartite graph which is an expander. I searched the web and didn't find any sufficient answer. The only explicit graph I did ...
misha312's user avatar
  • 209
1 vote
0 answers
89 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 ...
sabya's user avatar
  • 11
1 vote
0 answers
88 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 ...
shiwang's user avatar
  • 481
1 vote
0 answers
91 views

Stable matching of producers, consumers and objects

Has the following version of the stable matching problem been studied? There are $k$ types of objects. There are $n$ producers, each of whom can produce a single object of any type, and has a ...
Erel Segal-Halevi's user avatar
1 vote
0 answers
54 views

How to maximize the number of buyers in a shop?

There is a shop which consists of N items and there are M buyers. Each buyer wants to buy a specific set of items. However, the cost of all transactions is same irrespective of the number of items ...
user3080029's user avatar
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
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
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
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
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
0 votes
1 answer
50 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 ...
user2994783's user avatar
0 votes
0 answers
73 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 ...
Sexy Whore's user avatar
0 votes
0 answers
74 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/...
Sexy Whore's user avatar
0 votes
0 answers
596 views

Hopcroft–Karp algorithm time complexity

In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph: https://dl.dropboxusercontent.com/u/64823035/04569670.pdf The ...
An Phung's user avatar
  • 109
-1 votes
1 answer
2k 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 ...
Nolan Robidoux's user avatar