Share Your Experience: Take the 2024 Developer Survey

# Tag Info

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, ...
• 161k
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 ...
• 8,248
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 ...
• 277k

### 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'...
• 277k
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 ...
• 507

### 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 ...
• 651

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

• 6,187

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

• 14.1k