10

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

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 ...


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

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

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

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

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

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

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.


5

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, ...


5

Set $V_i' = V_i \cap V'$. You can solve this by finding the maximum matching using at most $k$ vertices from $V_1'$ and at most $x-k$ from $V_2'$ for all $k \in [0, x]$. This in turn can be found with maximum flow. To find this maximum matching, we modify the usual reduction to maximum flow. Let $s$ be the source and $t$ the sink. Let $l$ and $r$ be ...


5

After some research, I found out that my question is a special case of the problem of priority matching. In this case there are two priority classes, $X_0$ and $X_1 := V\setminus X_0$. The goal is to find a matching that maximizes the number of saturated vertices in $X_0$, and subject to that, the number of saturated vertices in $X_1$. There are efficient ...


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

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.


4

The short answer is, Player two wins if and only if the corresponding graph admits a matching that "covers" the set $H$. Here is a bit of explanation. Your idea is almost right. However, the proof is not intuitive and you might miss some details which you need if it is a theoretical question or if you need to design the exact winning strategy and not only ...


4

Here is a simple algorithm to get you started. Compute all $\binom{n}{2}$ pairwise distances, and put them in an array $A$. For each pair $a<b$ in $A$, use a bipartite matching algorithm to determine whether there is a matching that uses only distances in the range $[a,b]$. Choose the pair minimizing $b-a$. In total, there are $O(n^4)$ invocations of the ...


3

Possible approach: If a bipartite graph is $d$-regular then it can be decomposed into $d$ perfect matchings by Hall's theorem. Any bipartite graph of maximal degree $d$ can be completed to a $d$-regular bipartite graph (possibly by adding vertices).


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 ...


3

This problem has been solved by Alon Efrat, Alon Itai and Matthew J. Katz in their paper Geometry Helps in Bottleneck Matching and Related Problems. The running time of the algorithm is $O(n^{1.5} \log n)$.


3

There is a simpler way to solve your problem, but just for fun, I'll outline a different approach that generalizes nicely. For a real-world implementation, the advantages should also be clear. You can cast this problem, and similar problems like Sudoku as constraint satisfaction problems. After modeling the problem, you can feed it to a state-of-the-art ...


3

The flow network $G'$ is constructed from the original bipartite graph $G=(L,R,E)$ by adding two new nodes $s,t$, connecting $s$ to all nodes in $L$, connecting all nodes in $R$ to $t$, and orienting all edges in $E$ from $L$ to $R$. And $s$-$t$ cut in $G'$ has the form $(S,\overline{S})$ where $s \in S$, $t \in \overline{S}$. The edges crossing the cut are: ...


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