Skip to main content
Share Your Experience: Take the 2024 Developer Survey
7 votes
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$...
dwajc's user avatar
  • 86
7 votes
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....
Juho's user avatar
  • 22.6k
6 votes
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 ...
Erel Segal-Halevi's user avatar
6 votes

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.
D.W.'s user avatar
  • 161k
5 votes
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 ...
David Richerby's user avatar
5 votes
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 ...
Yuval Filmus's user avatar
5 votes
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 ...
Antti Röyskö's user avatar
4 votes
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 ...
tjhighley's user avatar
  • 507
4 votes
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 ...
Banach Tarski's user avatar
4 votes
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 ...
Discrete lizard's user avatar
  • 8,248
4 votes
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 ...
D.W.'s user avatar
  • 161k
4 votes
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. ...
David Richerby's user avatar
4 votes
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.
Yuval Filmus's user avatar
4 votes
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 ...
Narek Bojikian's user avatar
4 votes

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 ...
Yuval Filmus's user avatar
4 votes
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. ...
Yuval Filmus's user avatar
4 votes
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 ...
Discrete lizard's user avatar
  • 8,248
3 votes

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 ...
Inuyasha Yagami's user avatar
3 votes

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 ...
Chris Okasaki's user avatar
3 votes

Polynomial time solution for bipartite matching

This actually has nothing to do with the stable marriage problem; it's an instance of bipartite matching. (It's not related to stable marriage, becuase you don't have an ordering on the preferences ...
D.W.'s user avatar
  • 161k
3 votes

Minimizing the overall cost over groups

You are probably looking for a solution to the following optimization problem. Weighted maximum biparite matching. Given a weighted bipartite graph $G=(U\cup V, E)$ with weights $w\colon U\times V \...
Lieuwe Vinkhuijzen's user avatar
3 votes

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

I believe the best algorithm known is Hopcroft and Karp, "An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs", SIAM Journal of Computing 2:4 (1973), pp 225-231.
vonbrand's user avatar
  • 14.1k
3 votes
Accepted

Does real linear programming produce bipartite perfect matching using maxflow reduction?

Let us consider $K_{2,2}$, the complete bipartite graph with two vertices on either side. A valid max flow sends $1/2$ units of flow across each edge of the bipartite graph. This gives a negative ...
Yuval Filmus's user avatar
3 votes
Accepted

Minimum cost to match $n$ people with $m$ shops

Your problem is an instance of minimum bipartite perfect matching. This is known as the assignment problem, and there are known efficient algorithms. As a first step, you should compute the weights ...
Yuval Filmus's user avatar
3 votes
Accepted

How to cover given entries in a matrix with minimum number of rows and columns?

Let $R=\{r_1, \cdots, r_n\}$ be the set of all rows. Let $C=\{c_1, \cdots, c_m\}$ be the set of all columns. If and only if the matrix entry at row $i$ and column $j$ is 1, we connect $r_i$ with $c_j$ ...
John L.'s user avatar
  • 39k
3 votes

Assignment Problem -- finding the $k$ agents with the best assignment

The assignment problem can be extended to solve this problem. The regular problem without the $k$ restriction can be solved by building a Minimum Cost Maximum Flow network is as follow: We have a ...
Marcelo Fornet's user avatar
3 votes
Accepted

Hardness of a scheduling/assignment problem

The problem is NP-hard, at least for a particular simplified configuration. Assume that each $m_l$ is effectively infinite - we can scan a particular libraries' books all on the day we get access. ...
orlp's user avatar
  • 13.6k
3 votes
Accepted

Saturated sets in bipartite graph

Let's fix a maximal matching $M$. Let $Z\subseteq Y$ be the set of nodes that are not matched to nodes in $X$. We can see a node $x\in X$ belongs to a saturated set if and only if there does not exist ...
xskxzr's user avatar
  • 7,455
3 votes

How to match two point sets to minimize total distance?

The planer (d = 2) version of the problem is called in several names such as Euclidean bipartite matching problem, Euclidean bichromatic matching problem, or Bipartite matching of planar points. The ...
pcpthm's user avatar
  • 2,428
3 votes

Bipartite matching with constraints on one part

The problem is not approximable in polynomial-time within a factor of $n^{1-\varepsilon}$ for any constant $\varepsilon>0$, unless $\mathsf{NP} = \mathsf{ZPP}$. To see this you can reduce from ...
Steven's user avatar
  • 29.5k

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