# Questions tagged [bipartite-matching]

The tag has no usage guidance.

126 questions
Filter by
Sorted by
Tagged with
32 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 ...
47 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 ...
25 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 ...
28 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 ...
53 views

222 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'$?
153 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 ...
308 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: ...
181 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 ...
107 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$. ...
97 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 ...
33 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 ...
83 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 ...
145 views

239 views

### Minimum cost to match $n$ people with $m$ shops

We are given coordinates of $n$ people and $m$ shops. We should find a matching such that each person is matched with exactly one shop, and one shop is matched with at most one person.The total cost ...
112 views

### How can I find matchings in a Bipartite graph beginning with specific vertices?

Context: I'm modelling kidney exchanges through directed acyclic graphs. I convert these to Bipartite graphs (by splitting each node into a donor and receiver, and the edge from the original graph ...
163 views

### Does real linear programming produce bipartite perfect matching using maxflow reduction?

Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram: We can formulate max flow as an linear programming problem with integer variables in ...
34 views

### Algorithm to assign producers to consumers with respect to connections

I am trying to analyze supply chains in a game and have come across this problem: First, an informal description: I have producers and consumers. Each producer produces a certain amount of goods, ...
35 views

### Hungarian Algorithm - Bipartite Graph Approach

I have been having some difficulty making sense of the Hungarian Algorithm outlined here. It seems incomplete and/or erroneous to me. The main issue is the line: If R_T ^ Z is nonempty, then ...
29 views

### Bipartite vertex cover [duplicate]

If this link can be any help https://codeforces.com/blog/entry/63164 A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A ...
999 views

### Vertex cover in bipartite graph from Hopcroft-Karp Algorithm

Vertex cover in bipartite graph is polynomial algorithm: by König's theorem the number of edges in a maximum matching is the number of vertices in a minimum vertex cover. I've implementated the ...
45 views

### Minimizing catastrophic risk in Gale-Shapley matching

In the hospital-resident assignment problem we have to match a large set of med students with a small set of hospitals. Hospitals may accept multiple students, but the number of students is much ...
1k views

### Maximum number of matched vertexes in a one-to-many bipartite graph

I have a variant of bidding problem at hand. There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who ...
262 views

### minimum cardinality maximal matching of graph

How to find minimum cardinality maximal matching? I tried that pick a edge from highest degree vertex remove other edges from same vertex and so on.
128 views