Questions tagged [bipartite-matching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
11
votes
1answer
324 views

How fast can we compute the size of maximum matching in an unweighted bipartite graph?

Is there a way to compute the size of a maximum matching in an unweighted bipartite graph more efficiently (e.g. faster) than computing a maximum matching? It is a long shot but it is often an ...
9
votes
2answers
615 views

Size of Maximum Matching in Bipartite Graph

Am I correct in my observation that the cardinality of the maximum matching $M$ of a bipartite graph $G(U, V, E)$ is always equal to $\min(|U|, |V|)$?
9
votes
2answers
1k views

Reducing max flow to bipartite matching?

There's a famous and elegant reduction from the maximum bipartite matching problem to the max-flow problem: we create a network with a source node $s$, a terminal node $t$, and one node for each item ...
8
votes
0answers
113 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 ...
7
votes
1answer
4k views

How to find the maximum independent set of a directed graph?

I'm trying to solve this problem. Problem: Given $n$ positive integers, your task is to select a maximum number of integers so that there are no two numbers $a, b$ in which $a$ is divisible by $b$...
7
votes
1answer
234 views

Given 2 sets of n points: minimize sum of traveled distances

I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean ...
7
votes
2answers
254 views

Find a minimum-cardinality Hall-violator

Given a bipartite graph $(X,Y,E)$, in which there is no perfect matching, I want to find a smallest subset that violates Hall's condition, i.e., a minimum-cardinality set $S \subseteq X$ for which $|...
6
votes
1answer
572 views

Complexity of Hopcroft-Karp

I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where ...
5
votes
3answers
921 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 ...
5
votes
2answers
522 views

In the Hopcroft-Karp algorithm, what is the purpose of the breadth first search?

In the Hopcroft-Karp algorithm for bipartite matching, I don't understand the purpose of the breadth first search. I think it's used to find a set of vertex disjoint augmenting paths, but I'm not ...
5
votes
2answers
466 views

Finding a subset in bipartite graph violating Hall's condition

We are given a bipartite graph of $n \leq 200$ vertices in both the first and the second partite set. Let $U$ be some set of vertices in the first set, and $V$ those vertices from the second that are ...
5
votes
1answer
1k views

Konig's Theorem for Min Weight Vertex Cover?

Koning's theorem states that the cardinality of the maximum matching in a bipartite graph is equal to the size of its minimum vertex cover. Wikipedia states that there is an equivalent version of the ...
5
votes
3answers
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 ...
5
votes
1answer
667 views

Hungarian Algorithm - Arbitrary Assignments

I've looked at several explanations of the Hungarian Algorithm for solving the Assignment Problem and the vast majority of these cover only very simplistic cases. The most understandable explanation ...
5
votes
1answer
376 views

Decomposing a bipartite graph of maximal degree d to d matchings

I have tried for the last few days to prove that any bipartite graph of maximal degree d may be broken into (at most) d matchings. My main approach is to prove this inductively over the maximal ...
5
votes
1answer
146 views

Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph?

Usually questions deal with claw-free graphs, but suppose we are given a graph $G$ and there are $k$ vertex-disjoing claws in the graph, how can we derive a randomised algorithm using color coding to ...
5
votes
0answers
555 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 ...
4
votes
2answers
6k views

The stable marriage algorithm with asymmetric arrays

I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices. ...
4
votes
3answers
2k views

Number of ways to fill a 2xN grid with M colors

This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri. In short, the question asked to find the number of ways to fill a $ 2\times N$ grid with $M$ colors such that no two ...
4
votes
1answer
24k views

Perfect matching in a graph and complete matching in bipartite graph

When I google for complete matching, first link points to perfect matching on wolfram. It defines perfect matching as follows: A perfect matching of a graph is a matching (i.e., an independent ...
4
votes
1answer
138 views

Bipartite graph question

Assume you are given a bipartite graph $G = (U, V, E)$ and you are given an integer $n$. Assume also that for each $v \in V$, you are given two integers $v_{min}$ and $v_{max}$ (where $v_{min} \le v_{...
4
votes
1answer
171 views

Term for a matching which is perfect on one side only

What is a standard term for a matching in a bipartite graph, in which one part has less vertices than the other part, and the part with less vertices is fully matched (but the other part is, obviously,...
4
votes
1answer
3k views

Stable marriage problem with only one side having preferences [duplicate]

I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and ...
4
votes
2answers
90 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 ...
4
votes
1answer
638 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, ...
4
votes
2answers
245 views

Auction where each bidder bids on a bundle of items

Is there some optimal solution in an auction where each bidder bids on a bundle of items?
4
votes
1answer
352 views

Maximum bipartite matching with extra reward for covering certain sets

Consider the following variation of Bipartite Maximum Matching. As usual, we have a bipartite graph $G$. In addition, there is an additional collection of sets $S_1,S_2,\dots,S_k$, with each set $...
4
votes
2answers
3k views

Finding a minimum weight perfect matching in Christofides TSP algorithm

Context: After creating the minimum spanning tree, the next step in Christofides' TSP algorithm is to find all the N vertices with odd degree and find a minimum weight perfect matching for these odd ...
4
votes
2answers
1k views

Bipartite Graph Game

So say we have a bipartite graph G=(X,Y,E). Let's make a game out of it. I go first. I pick a node in X. You go next. You pick a node in Y that is connected by an edge to the node I picked. Next it's ...
4
votes
1answer
143 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\...
4
votes
1answer
107 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 - $...
4
votes
1answer
73 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 ...
4
votes
2answers
715 views

Maximum bipartite matching when some nodes must be matched

Consider the problem of finding a maximum cardinality bipartite matching under the additional condition that some set $S$ of nodes (all lying on the same side of the bipartition) must be matched. ...
4
votes
1answer
393 views

Assignment problem with no cost

I have a problem that I was able to conceptualize as following: Problem We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination ...
4
votes
1answer
72 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 ...
4
votes
1answer
79 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 ...
3
votes
1answer
3k views

Find perfect matching whose weight is minimal, in polynomial time

Given a bipartite graph $G=(A,B,E)$ and a weight function $w: E \rightarrow\mathbb{R}^+$, I'd like to find a perfect matching $M\subseteq E$ with min. weight. I'm assuming $|A| \leq |B|$, and WLOG $G$ ...
3
votes
1answer
182 views

Why is bipartite perfect matching a special case of clique problem?

In Lovász writes [1] : bipartite graph has a perfect matching, which is a special case of the clique problem Why is bipartite perfect matching a special case of clique problem? The Work of A.A. ...
3
votes
1answer
738 views

Number of Matchings in a Bipartite

Given two sets A and B of sizes |A| = n and |B| = m, where m >= n. There are edges from set A to set B. I need to find the number of matchings where all of vertices ...
3
votes
1answer
2k views

Existence of bipartite perfect matching

Let $B = G(L, R, E)$ be a bipartite graph. I want to find out whether this graph has a perfect matching. One way to test whether this graph has a perfect matching is Hall's Marriage Theorem, but it is ...
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 ...
3
votes
1answer
51 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$. ...
3
votes
1answer
23 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 ...
3
votes
1answer
939 views

Clarification with Kuhn-Munkres/Hungarian Algorithm

I have been attempting to get my mind around the Kuhn-Munkres/Hungarian Algorithm. I have been using the following statement of the algorithm which I found here. Based on my readings on the algorithm,...
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 ...
3
votes
1answer
865 views

What is the best algorithm to match a student's schedule with a tutor's schedule?

I am building an application (RoR framework) that can help to match a tutor and a student based on their subjects, budgets, locations and freetime. I have done the first three parts(subjects, budgets, ...
3
votes
1answer
184 views

3✕n chessboard with holes - maximum number of knights not attacking each other

I'm trying to to create an algorithm (working in polynomial time) to solve the following problem: What maximum number of knights that any two of them don't attack each other can be placed on a 3✕n ...
3
votes
0answers
89 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 $...
3
votes
0answers
45 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 ...
3
votes
0answers
85 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 ...