Share Your Experience: Take the 2024 Developer Survey

# Tag Info

Accepted

### Reducing max flow to bipartite matching?

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$...
• 86
Accepted

### Problems that are easy on bipartite but hard on general graphs

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....
• 22.6k
Accepted

### Find a maximum matching that saturates a given set of vertices

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 ...
• 6,030

### How to match two point sets to minimize total distance?

This is an instance of the assignment problem and can be solved with standard algorithms for that problem.
• 161k
Accepted

### Why is bipartite graph matching hard?

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 ...
• 81.8k
Accepted

### Perfect matching in a bipartite regular graph in linear time

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 ...
• 277k
Accepted

### Maximum matching in a bipartite graph

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 ...
• 1,131
Accepted

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

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 ...
• 507
Accepted

### Konig's Theorem for Min Weight Vertex Cover?

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 ...
• 1,208
Accepted

### Changing preference in Gale-Shapley algorithm?

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 ...
• 8,248
Accepted

### Auction where each bidder bids on a bundle of items

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 ...
• 161k
Accepted

### Determine whether two collections of items can be paired

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. ...
• 81.8k
Accepted

### Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?

Your problem is the same as interval graph coloring. There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.
• 277k
Accepted

### Winning strategy for a given game on graphs

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 ...
• 4,474

### Minimize range of distances between two sets of points

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 ...
• 277k
Accepted

### Find a perfect matching with weights as close as possible to each other

You haven't specified what you mean by "as close as possible to each other", so let me assume that you want to minimize the difference between the minimal weight and the maximal weight. ...
• 277k
Accepted

### Why does Hopcroft-Karp only work on bipartite graphs?

I don't see why bi-directional edges are relevant here (or what problem your construction tries to solve), the question you reference is only about undirected graphs. But I can understand your ...
• 8,248

### Find a minimum-cardinality Hall-violator

This problem is $\mathsf{NP}$-hard. The problem is also known as Hall set problem and there is a reduction from Clique problem. See Theorem 3.2.5 from this thesis. I was thinking along the direction ...
• 6,187

### Hungarian Algorithm - Arbitrary Assignments

See Finding all minimum-cost perfect matchings in Bipartite graphs. Once you run the Hungarian Algorithm, you can use the result to find all "admissable" edges. Roughly speaking, admissable edges ...