The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Tag Info

Hot answers tagged bipartite-matching

12

Given a bipartite graph $G = (U,V,E)$ and a maximum matching $M$ of $G$, via Konig's Theorem we see that $|M| = |C|$ where $C$ is a minimum vertex cover for $G$. Your statement is merely an upper bound on the size of the possible matching, not a strict equality. The image on the wikipedia page provides a nice counterexample to your claim. We see that $|M| = ... 9 No. For example, consider the case where the two sides are disconnected$|E| = 0$or the case where a large group of nodes are all connected to the same single node:$U = u_1, u_2, ..., u_nV = v_1, v_2, ... , v_nE = u_1v_1, u_2v_1, ... u_nv_1, v_1u_1, v_2u_1, ... v_nu_1$9 The correct running time is indeed probably$O((m+n)\sqrt{n})$. However, this is a mouthful, and the expression$O(m\sqrt{n})$looks nicer and is also more succinct. In most cases,$m \geq n/2$, since otherwise there is an isolated vertex. In fact, by finding isolated vertices, we can improve the running time of the algorithm to$O(n + m\sqrt{n})$. An ... 7 Yes, the stable marriage problem still makes sense with unequal arrays. Permit me to use men and women as opposed to students and dorms. There are different stable matchings that you can ask for resulting in different cases. A specific stable matching is desired, either male optimal or female optimal solution Any valid stable matching is desired All the ... 7 Your problem is NP-hard, by reduction from set cover. Given an instance of set cover with universe$V$, sets$U$and number$n$, draw an edge between a set and a point if the set contains the point. Let$v_\min = 1$and$v_\max = |U|$. A subset$U'$satisfies the$v_\min,v_\max$constraints iff it is a set cover. So if there is a set cover$W$of size$m \...

7

Yes, there is a polynomial-time algorithm for your problem. There's no need to use a LP or ILP; you can solve it directly using combinatorial, graph-based methods. In particular, we can solve your problem by a reduction to the assignment problem, i.e., to computing a maximum weight matching in a weighted bipartite graph. Suppose we have a bipartite graph ...

7

These are two different concepts. A perfect matching is a matching involving all the vertices. A bipartite perfect matching (especially in the context of Hall's theorem) is a matching in a bipartite graph which involves completely one of the bipartitions. If the bipartite graph is balanced – both bipartitions have the same number of vertices – then the ...

7

There are several well-known NP-complete problems that become solvable in polynomial-time for bipartite graphs. For example, 3-coloring is easy as bipartite graphs are precisely the 2-colorable graphs. Another example is independent set which is made easy by König's theorem. Wikipedia also lists a problem that is NP-hard for general graphs but is trivially ...

7

Strangely enough, no such reduction is known. However, in a recent paper, Madry (FOCS 2013), showed how to reduce maximum flow in unit-capacity graphs to (logarithmically many instances of) maximum $b$-matching in bipartite graphs. In case you are unfamiliar with the maximum $b$-matching problem, this is a generalization of the matching, defined as follows:...

6

You are trying to find the width of the poset defined by the given subset of integers and the divisibility relation. The width is the maximum number of anti-chains, which is the same as the maximum set of incomparable elements in the poset. This corresponds exactly to the maximum independent set in the Comparability Graph, where each integer is a vertex and ...

6

A matching in which all the vertices in $A$ are matched is known as a perfect matching. When $n = m$, you need to compute the permanent of the bipartite adjacency matrix (defined in the same way as the determinant, only without the signs). This is conjectured to be rather difficult unfortunately, even in this special case in which the matrix in question is ...

6

Let $G=(V,E)$ be the bipartite graph. Construct a new graph $G'=(V',E')$ whose vertices are the edges of $G$, and where we add $(e,e')$ to $E'$ if $e,e'$ are two edges from $G$ that don't touch each other (don't have an endpoint in common). Now there's a matching of size $s$ in $G$ if and only if there's a clique of size $s$ in $G'$. In particular, there'...

5

Vertex-disjoint means that no vertex appears in two augmenting paths. The paths have to be disjoint so that all can be used. If we have two augmenting paths, P1 and P2, and we augment the matching using using P1, is P2 still an augmenting path for the augmented matching? Yes, if P1 and P2 are vertex disjoint. As for minimum length, it has the practical ...

5

A quick literature review suggests that the fastest algorithm for deciding whether a dense bipartite graph has a perfect matching is still the matrix algorithm, which runs in time $O(|V|^\omega)$. You can reduce the space of the algorithm, see Isolation, Matching and Counting by Allender, Reinhardt and Zhou. A recent paper from 2010, which focuses on planar ...

5

You can use inclusion-exclusion. There are $M!/(M-N)!$ choices for the first row. Fix these choices. The number of choices for the second row in which $T$ specific columns are bad (but the row itself is good) is $(M-T)!/(M-N)!$. According to the inclusion-exclusion principle, the required number is  \frac{M!}{(M-N)!} \sum_{T=0}^N (-1)^T \binom{N}{T} \frac{(...

5

You can add $5$ dummy students, and put them low in the dorms' preference order. The resulting perfect matching $\pi$ will have the following two properties: There is no student $s$ and dorm $d$ which are not matched such that $s$ prefers $d$ to $\pi(s)$ and $d$ prefers $s$ to $\pi(d)$. There is no student $s$ and empty dorm $d$ such that $s$ prefers $d$ to ...

5

I think it is still the standard bipartite maximum matching problem, which can be solved by the algorithm of Hopcroft and Karp. You put an edge in the bipartite boys-girls graph, iff you have mutual attraction. Then you maximize your matching and voilà. Notice that if you would never assign a boy to a girl with one-sided attraction, since this does not ...

5

Let $G=(X,Y,E)$ be a bipartite graph with $|X|=|Y|=n$ having a maximum matching $M$. Consider the directed graph $G'$ on the vertex set $X \cup Y$ which includes the edges of $G$ oriented from $X$ to $Y$ and the edges of $M$ oriented from $Y$ to $X$. Let $U \subseteq X$ be the set of vertices of $X$ unmatched in $M$, and let $S$ be the set of vertices ...

5

The answer to your first question is: yes, there is a simple augmentation. It is described in the standard literature on the stable marriage problem. See the Wikipedia article for references in the literature where this is described. It is also described here: The stable marriage algorithm with asymmetric arrays. See also https://cs.stackexchange.com/a/...

5

The Wikipedia page on König's theorem gives an algorithm that converts a maximum matching to a minimum vertex cover. I'm not sure that an algorithm for finding maximum matching can be tweaked to an algorithm for finding minimum vertex cover in any other way, though it's perfectly possible.

5

Such a matching is said to saturate one of the sides. More specifically, if $M$ is a matching of a graph $G$ and $v$ is incident to one of the edges of $M$, we say that $M$ saturates $v$. If $A$ is a set of vertices, then we say that $M$ saturates $A$ if every vertex in $A$ is saturated by $M$. Specifically for your case, the matching saturates the ...

5

I am reading on how [...] to solve unweighted bipartite graph matching problem. [...] The goal of the problem seems to be to find a maximum matching in a complete bipartite graph No, the goal of the problem is to find a maximum matching in any unweighted bipartite graph.

4

This problem is NP-hard, by reduction from 3-dimensional matching. An instance of 3-dimensional matching involves three disjoint vertex sets $X,Y,Z$ and a set $T \subseteq X \times Y \times Z$ of triples of the form $(x_i,y_j,z_k)$. The goal is to find a subset $T_0 \subseteq T$ such that each vertex of $X \cup Y \cup Z$ appears in at most one triple of $... 4 As mentioned in the problem statement, this is the Assignment Problem (minimum weight bipartite matching) where it is known that the weights are the Euclidean distances. There have been several improvements since the Hungarian Algorithm, at least in terms of asymptotic bounds. Depending on the exact size of the graph, any of several algorithms may be the ... 4 So I found the answer. The equivalence is that the min weight vertex cover of a bipartite graph can be computed as the maximum flow in a related bipartite graph. In the unweighted case, this maximum flow corresponds to the maximum carnality matching in a bipartite which is exactly the version of Konig's theorem that we all know and love. For the sake of ... 4 The property your wish to prove is known as strategy proofness: Is it possible for an agent to report a preference$P'$such that it gets matched to a strictly better result w.r.t. its true preference$P\$ than reporting truthfully? Note that while the GS algorithm is strategy proof for the men, it is not for the women: they can use misrepresenting the ...

4

There is a classical linear time algorithm of Gabow and Kariv. The first step is to find an Eulerian tour. You do this by starting at an arbitrary vertex and following an arbitrary path until you close a cycle. If you're not back where you started, you continue following an arbitrary path until closing a cycle, and so on. If you are back where you started, ...

4

Yes. You're just looking for a maximum matching in the bipartite graph where one side is the items, the other side is the slots and there's an edge between an item and each slot it's compatible with. There are a number of efficient algorithms for this. The standard method taught to CS undergraduates is the augmenting paths algorithm of Hopcroft and Karp.

3

Assignment Problem would be one such example: There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way ...

Only top voted, non community-wiki answers of a minimum length are eligible