Questions tagged [bipartite-matching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
2answers
42 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 ...
4
votes
1answer
52 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 ...
0
votes
1answer
30 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 ...
0
votes
1answer
24 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 ...
5
votes
1answer
118 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 ...
2
votes
0answers
30 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
0answers
55 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
0answers
57 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
1answer
39 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)...
4
votes
1answer
210 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'$?
2
votes
1answer
150 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 ...
7
votes
1answer
174 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 ...
3
votes
1answer
97 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$. ...
1
vote
1answer
278 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: ...
3
votes
1answer
30 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 ...
4
votes
1answer
90 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 ...
2
votes
2answers
74 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 ...
0
votes
0answers
15 views

Maximum cardinality bipartite matching when nodes are ordered and only subsets can be matched?

Maximum bipartite matchine problem can be converted to the maximum flow problem and it can be solved by Edmonds-Karp algorithm in O(VE)<=O(V^3). But there can be bounded problem, when the nodes on ...
3
votes
0answers
129 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 $...
0
votes
0answers
30 views

Counting step in Gale-Shapley Algorithm(Deferred Acceptance Algorithm)

Imagine there is a modified version of many-to-one school choice matching with Deferred Acceptance Algorithm(DAA): other things will be the same as original DAA, except that for an unassigned student, ...
1
vote
1answer
63 views

Maximum-cardinality matching in unbalanced bipartite graphs

Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$. The Hopcroft-Karp algorithm runs in time $O(|E|\sqrt{|V|})$, where here $|V| = |X|+|Y|$. So ...
1
vote
1answer
40 views

Student Course Allocation Problem with Many Constraints [closed]

Problem statement In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students. $i$-th section has: A student capacity: $cap_i$. Two lecture timings. (Formally, each ...
0
votes
0answers
10 views

How to assign people to categories based on some voting rules?

Say in an election there are predefined categories users can be assigned to. Of the people who are assigned to a certain category, other users can vote for them. To compute the results, the following ...
3
votes
0answers
58 views

Alternative criterion for approximate maximum-weight perfect matching algorithms [closed]

Is there any literature on approximate maximum-weight perfect matchings where the approximation criterion is not the factor between the approximate and exact weight sum achieved by each solution, but ...
1
vote
0answers
18 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 ...
4
votes
1answer
85 views

Term for a graph decomposition based on a maximum matching

Let $M$ be a maximum cardinality matching in a bipartite graph $G(X+Y,E)$. Let $X_0$ be the subset of $X$ unmatched by $M$. Define the following sequence: $Y_1 = $ the neighbors of $X_0$ using edges ...
4
votes
1answer
212 views

Matching Algorithm - How to maximize matched quantity with unique matching rules?

Given a set $S=\{A,B,\cdots,H\}$. Elements in $S$ can be matched according to the following rules: $$\begin{aligned} A\leftrightarrow B\\ C\leftrightarrow D\\ B+C\leftrightarrow F\\ D+A\...
1
vote
2answers
92 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 ...
4
votes
2answers
141 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 ...
1
vote
1answer
32 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, ...
1
vote
1answer
33 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 ...
0
votes
0answers
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 ...
3
votes
2answers
44 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 ...
0
votes
1answer
247 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.
1
vote
1answer
77 views

Matching schedules between users and providers

I have a problem I've been dealing for the past few days, and I'm pretty stuck. Each user has a schedule for a given week, such as ...
4
votes
1answer
119 views

Finding a subset with few neighbors

Given a bipartite graph $G(X+Y,E)$, how can I find a non-empty subset $Y'\subseteq Y$, such that $|N(Y')| \leq |Y'|$ (where $N$ is the set of neighbors)? If $|Y|\geq |X|$ then the problem is easy - $...
2
votes
1answer
321 views

Using LP to prove the max matching - min cover theorem

Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following ...
1
vote
2answers
81 views

Either find a perfect matching, or return a witness that none exist [duplicate]

I am looking for a polynomial-time algorithm that takes as input a bipartite graph $(X\cup Y, E)$, and returns one of two options: If a perfect matching exists, it returns the matching; Otherwise, it ...
2
votes
1answer
187 views

Multiple rounds of bipartite matching problem

I have a set of investors (say n), and a set of startups (say m). At the start, I have all the investors say either yes or no to the startup (which corresponds to whether they want to interact with ...
0
votes
1answer
82 views

More efficient maximum bipartite matching

I've been looking into weighted matching in bipartite graphs and am currently looking at maximum matchings in weighted bipartite graphs. As I've been reading and poking around at different books and ...
1
vote
0answers
72 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 ...
2
votes
0answers
52 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 ...
3
votes
1answer
27 views

Determine whether two collections of items can be paired

Given collections I (items) and S (slots), where I >= S. And a pairing function that ...
4
votes
1answer
109 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 ...
2
votes
2answers
37 views

Can a perfect matching always be found by a picking sequence?

There are $n$ people and $n$ items. For each person, there is a set of items he likes. Our goal is to give to each person a single item that he likes, i.e, find a perfect matching in the preference ...
1
vote
0answers
61 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 ...
2
votes
1answer
1k views

Perfect matching in a bipartite regular graph in linear time

Given a $G=(V,E)$ bipartite, undirected, 4-regular graph, I would like to find a perfect matching in linear time. It is easy to show that there is a perfect matching for the graph, by using flow and ...
2
votes
1answer
424 views

Bipartite Perfect Matching “Assignment Problem” - finding an assignment of a particular weight

The assignment problem is to find the minimum weight perfect matching in a weighted bipartite graph. This problem can be solved using the Hungarian algorithm in polynomial time. It is also possible to ...
4
votes
1answer
862 views

Changing preference in Gale-Shapley algorithm?

Suppose, in the context of the classic marriage problem, two equal size groups of $n$ men and $n$ women are being matched, with the GS algorithm. If a man were to switch the order of a pair of women, ...
8
votes
0answers
136 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 ...