Questions tagged [bipartite-matching]
The bipartite-matching tag has no usage guidance.
28
questions with no upvoted or accepted answers
8
votes
0
answers
269
views
Complexity of removing edges to eliminate a perfect matching
Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this ...
- 81
5
votes
0
answers
738
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 ...
- 161
3
votes
0
answers
321
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 $...
- 519
3
votes
0
answers
138
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 ...
- 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 ...
- 651
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
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
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 ...
2
votes
0
answers
60
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 ...
- 21
2
votes
0
answers
79
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,...,...
- 41
2
votes
0
answers
699
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 ...
- 135
2
votes
0
answers
317
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 ...
- 171
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
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
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
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
0
answers
45
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 ...
- 209
1
vote
0
answers
84
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 ...
- 11
1
vote
0
answers
80
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 ...
- 461
1
vote
0
answers
90
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 ...
- 5,844
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 ...
- 111
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 ...
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
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
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
0
answers
578
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 ...
- 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 ...
- 101