Skip to main content
Share Your Experience: Take the 2024 Developer Survey
14 votes
Accepted

A problem with the greedy approach to finding a maximal matching

You're correct, you're not missing anything -- except that the algorithm is not wrong. The task is to choose a maximal matching, not a maximum matching. There may be many possible maximal matchings, ...
D.W.'s user avatar
  • 161k
8 votes
Accepted

What is a fractional matching?

Given a graph $G=(V,E)$, we can represent a matching as a function $f$ from the edges $E$ to $\{0,1\}$ such that for each vertex $v\in V$, we have $\sum_{w\in N(v)} f(v,w) \leq1$, where $N(v)$ is the ...
Discrete lizard's user avatar
  • 8,248
7 votes
Accepted

Show that the following algorithm doesn't always find the optimal matching

Consider a graph consisting of two triangles connected by an edge (a total of seven edges). Using this graph, Besser and Poloczek show that no greedy-like algorithm for maximum matching can be optimal ...
Yuval Filmus's user avatar
7 votes

Game on the graph with matchings

First of all, let me correct maximal matchings (that is, matchings which cannot be extended) to maximum matchings (that is, matchings of maximal size). Suppose first that the starting vertex $v$ doesn'...
Yuval Filmus's user avatar
6 votes
Accepted

Set of vertex-disjoint cycles maximizing different colored vertices

It cannot be solved in polynomial time, assuming P$\,\neq\,$NP. Without worrying about colors (i.e. if every vertex had the same color), it is the MAX SIZE EXCHANGE problem from the Kidney Exchange ...
tjhighley's user avatar
  • 507
6 votes

What is a fractional matching?

To add to Discrete lizard's answer, I would recommend you look into mathematical programming and optimization. The matching problem can be modelled as what is called an integer program (in fact the ...
NaturalLogZ'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

Correctness proof: 2-approximation of greedy matching-algorithm

Let $M$ be a maximal matching in the graph $G$. Let $M'$ be the matching returned by our approximation algorithm (obviously this algorithm returns a valid matching). For all $e\in M'$ let $M_e\...
Ariel's user avatar
  • 13.4k
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

Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you ...
John L.'s user avatar
  • 39k
5 votes
Accepted

Can maximum matching algorithms be used for maximum weight matching?

Ran Duan and Seth Pettie survey maximum matching algorithms in their 2014 paper Linear-Time Approximation for Maximum Weight Matching. In particular, Table III in their paper (page 5) lists algorithms ...
Yuval Filmus's user avatar
4 votes

state of the art of subset, set containment and partial match queries

I am not sure if this is "state of the art" but take a look at this paper Efficient subset and superset queries.
Teodor Dyakov's user avatar
4 votes

Matching two people. One has 7% in common with the other. The other has 70% in common. What's a fair match score?

It seems you're looking for a symmetric set similarity measure. (Symmetric since, as you point out, $A$ should match $B$ as much as $B$ matches $A$. Set similarity since each person's preference is ...
SamM's user avatar
  • 1,702
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

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

Maximum matching using linear programming

This approach is described by Grötschel, Lovász and Schrijver in their paper The ellipsoid method and its consequences in combinatorial optimization, as well as in their book Geometric algorithms and ...
Yuval Filmus's user avatar
4 votes

What is a fractional matching?

The formal definitions are very nice, but here's a simplier more intuitive explanation. In a fractional matching, every edge has a number. The sum all all the edge numbers connected to any vertex must ...
Keatinge's user avatar
  • 311
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

one-to-many matching in bipartite graphs?

This problem is called the B-matching problem. Where you are given a function $b:V \rightarrow \mathbb{N}$ that assign a capacity to each vertex and a function $u:E \mapsto \mathbb{N}$ that assigns a ...
Narek Bojikian's user avatar
4 votes
Accepted

Weighted Online Matching - randomized algorithms

A randomized algorithm cannot be constant-competitive in worst-case order. A proof using Yao's principle can be found here.
Erik's user avatar
  • 56
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

Partitioning a graph into connected pairs and triplets

The problem can be solved in the polynomial time for $k = 3$. There is this paper by Chen et al.. The authors design an approximation algorithm for the minimum $3$-path partition problem. The minimum $...
Inuyasha Yagami's user avatar
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
Accepted

Matching points between 2 polygons

This is a large topic, often called "geometric shape matching." Here is one survey that can lead to many specific algorithms: H. Alt and L. J. Guibas. Discrete geometric shapes: Matching, ...
Joseph O'Rourke's user avatar
3 votes

Find a maximum matching in linear time

$M\gets\emptyset$ While $E\neq\emptyset$ do select $(u,v)\in E$ $M \gets M \cup \{(u,v)\}$ delete all edges incident to $u$ and $v$ Return $M$ The above algorithm runs in $O(m+n)$ time if we store $...
kxxwz's user avatar
  • 31
3 votes
Accepted

Equality of cardinality of maximum matching and minimum vertex cover in general

Let $M$ be a maximum matching. Any vertex cover must contain at least one vertex out of each edge in the matching. Hence the size of a minimum vertex cover equals the size of the maximum matching if ...
Yuval Filmus's user avatar
3 votes

Sampling perfect matching uniformly at random

If you assume that your graph is planar, then there is a polynomial time procedure for this sampling problem. First, the problem of counting the number of perfect matchings is in P for planar graphs. ...
Elle Najt's user avatar
  • 374
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

Group tuples to satisfy constraints

I suggest expressing this as an instance of integer linear programming (ILP). Express boolean logic operations in zero-one integer linear programming (ILP) might be useful to you in figuring out how ...
D.W.'s user avatar
  • 161k

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