# Questions tagged [matching]

A matching (aka **Independent Edge Set**) in a simple graph is the set of pairwise non-adjacent edges i.e. no two edges have common vertex.

167 questions
Filter by
Sorted by
Tagged with
21 views

### Maximum cardinality matching of maximum weight

Given a graph, I want to find the matching with the maximum size in terms of edges, but among those matchings, given a real weight function on the edges, the one with the maximum weight. Is there an ...
18 views

### Concept of M-augmenting path to find a larger matching than $M$

I'm reading section 16.1 of the book, Combinatorial optimization, Polyhedra and efficiency by Schrijver. Here, he starts with a matching $M$ and describes a path $P$ that is $M$-augmenting if: The ...
22 views

### splitting of people betwen groups with group prioritiy list per person

Looking for an algorithm for splitting a list of people (S) into groups (G), |S| <= |G|, more than one person wants to be in a certain group. Every person has a monotone ranking from highest (most ...
63 views

### How difficult is this matching-like problem?

Let $A$ and $B$ be two sets of integers with $|A|>|B|$. Given a map $f: A \rightarrow B$ and $i \in A, j \in B$, let us use the shorthand "$i$ is matched to $j$" if $f(i)=j$. I am ...
183 views

### Game on the graph with matchings

The game on the graph $G$ is defined as follows. Initially, the chip is located at one of the vertices (let's call it the starting one). The players take turns, on each move it is necessary to move ...
15 views

### Maximal vs maximum matchings

Let $M_1$ be an inclusion-maximal matching in $G$ (that is, there is no matching which strictly contains it), and $M_2$ a maximum-size matching in $G$. How to prove that $|M_2| \le 2|M_1|$?
40 views

### Independent sets into which all the vertices of the graph can be split

How to prove that if $G$ is an acyclic transitive digraph, then the least independent sets into which all vertices of G can be divided is equal to the size of the longest paths to $G$?
24 views

### Set of cycles in directed graph

I have a directed graph. How to find in it some set of cycles that are pairwise do not intersect, but cover the entire set of vertices, if a cycle from one vertex is not considered a cycle, but cycle ...
22 views

### Maximum one-to-many matching

Let $G = (X+Y,E)$ be a bipartite graph and $k\geq 1$ an integer. A maximum $k$-matching is a subset of $E$ in which each vertex of $X$ is adjacent to at most $k$ edges and each vertex of $Y$ is ...
46 views

### Combinatorial Problem similar in nature to a special version of max weighted matching problem

I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem. I have a ...
46 views

### Why did Hopcroft and Karp write $M_0, M_1, M_2, \cdots, M_i, \cdots$? (Hopcroft - Karp Algorithm)

I am reading “An $n^{\frac{5}{2}}$ Algorithm for Maximum Matchings in Bipartite Graphs” by Hopcroft and Karp. Please see the image below. Let $s$ be the cardinality of a maximum matching. I think any ...
183 views

### Weighted Online Matching - randomized algorithms

Let's consider the edge weighted online matching problem. The Vertices arrive online and reveal all their current edges and edge-weights $w_e>0$. The goal is to maximize the matchings weight. An ...
36 views

### Is there such a problem as b-Matching with different b values?

Consider a bipartite Garph $G=(L \cup R, E)$. Naturally, a b-Matching problem is to find a set of edges $M \subset E$, such that each node in $L$ and $R$ are adjuscent to maximum $b$ neighbors, and a ...
17 views

### How to generate a uniform random sample of unique vertex pairings from a undirected graph under constraint?

I'm working on a research project where I have to pair up entities together and analyze outcomes. Normally, without constraints on how the entities can be paired, I could easily select one random ...
15 views

### A request for literature on Matching your partner problem

I need reference for a good book (a title and an author will do) or reference on the web which explains the problem of matching procedures of suitable partners between several males and females based ...
80 views

### Are these problems NP-Complete?

I got 2 decision problem that I need to answer if they are in P or they are NP complete: 1.Just like subset sum: given the integers or natural numbers $w_{1},\ldots ,w_{n}$ does ...
23 views

### Stable matching with dynamic preference lists

I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same ...
21 views

### Blossom Algorithm

I have noticed that in the blossom algorithm, we need to find the blossom while finding the augmenting path. What will happen if I just know there is a blossom in a graph and the contracted graph has ...
47 views

### Special case of stable marriage

I have an instance of the stable marriage problem in which the first side $S_1$ has $n_1$ agents and the second side $S_2$ has $n_2$ agents with $n_2$ is very big in comparison to $n_1$. In addition, ...