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.

49 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
157 views

Complexity of removing edges to eliminate a perfect matching

Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this ...
4
votes
0answers
139 views

variant of the stable roommates problem

The Stable Roommates Problem matches 2n participants into n sets of roommates based off of each participant's list of preferences. I was wondering if there was a variant of this problem where the ...
3
votes
0answers
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 ...
3
votes
0answers
136 views

Edmond's Blossom algorithm (Maximum Matching) explanation

I asked this question on Math Stackexchange but it didn't get much attention, so I am asking it here. Edmond's Blossom algorithm (Wikipedia), or simply the blossom algorithm, is a popular graph ...
3
votes
0answers
535 views

Optimal pairing of points in a set

I have an even number of points, each with coordinates $(x, y, z)$. I need to group these points into pairs. The cost of pairing two points is the Euclidean distance between them. I'd like to find the ...
3
votes
0answers
55 views

Properties of the filtered preference list (phase 1) in the Stable Roommates problem

I'm currently working my way through An Efficient Algorithm for the “Stable Roommates” Problem by Robert Irving (Journal of Algorithms, 6:577–595, 1984). On page 7 the paper starts with ...
3
votes
0answers
148 views

Construct matching for half of the vertices, in linear time

Suppose we have a graph $G=(V,E)$ connected and $K_{1,3}$-free. Sumner proved that every claw-free connected graph with an even number of vertices has a perfect matching (so, it is maximum matching). ...
3
votes
0answers
93 views

Hardness of a special case of maximum matching

Input: A set of $n$ Users $U=\{u_1, ..., u_n\}$ and a set of $m$ products $I=\{i_1, ..., i_m\}$. Associated with each pair $u \in U$ and $i \in I$ is the probability $p_{u,i}$ of $u$ purchasing the ...
2
votes
0answers
61 views

Matching of two weighted graphs allowing one-to-many mapping

I am looking for a heuristic for a graph matching problem as follows. Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
2
votes
0answers
154 views

Maximum weighted matching for directed (non-bipartite) graphs

This post concerns mainly non-bipartite graphs. Edmonds (1961) have proposed the Blossom algorithm to solve the maximum matching problem for undirected graphs. The best implementation of it is due ...
2
votes
0answers
298 views

Perfect matching in complete, weighted graph

I'm trying to find pairs in a complete, weighted graph, similar to the one below (weights not shown). For each possible pair there is a weight and I would like to find pairs for including all ...
2
votes
0answers
33 views

Looking for a matching-like mapping with a spread constraint

I am doing a project on task assignment with geographic constraints which naturally leads to the following question. Let $\mathbb{N}$ denote the set of integers. Given a finite subset $A \subset \...
2
votes
0answers
67 views

Complexity class of a counting problem

Consider the following inequalities: $\sum_j a_{ij}x_{ij}=1 \;\;\; i=1,...,n$ $\sum_i a_{ij}x_{ij} \le y_i \;\;\; j=1,...,n$ $x_{ij} \ge 0 \;\;\; i,j=1,...,n$ $y_i \in \{0,1,2\} \,\,\,\, i=1,...,...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
40 views

String matching problem needed some explanation

This is a question from CLRS book. (Chapter 32, string matching, the question is the problem for the whole chapter, it's in the end of the chapter) Let $y^i$ denote the concatenation of string y ...
1
vote
0answers
37 views

Online Many-to-one Matching

Offline Problem I have a graph $\mathcal{G} = (\mathcal{D} \cup \mathcal{A}, \mathcal{E})$. Each edge $e \in \mathcal{E}$ between the two vertex sets $\mathcal{D}$ and $\mathcal{A}$ has an ...
1
vote
0answers
24 views

Optimal matching of individuals in vehicles

I am looking for an algorithm to find the optimal matching/allocation of n individuals in m identical vehicles. The aim is to create groups of individuals who will share these vehicles. Groups' size ...
1
vote
0answers
116 views

Find a minimum weight matching of a specific size

Given a positive-weighted complete graph $G=(V,E)$ and an even integer $k$, I want to find a minimum weight matching of size exactly $k$, i.e., I want to choose $k/2$ vertex disjoint edges such that ...
1
vote
0answers
99 views

Computing a shortest $M$-alternating walk (for the Blossom algorithm)

When explaining the Blossom algorithm for maximum (nonbipartite) matchings, Shrijver describes, given a simple graph $G = (V,E)$, a matching $M \subseteq E$, and the set $X \subseteq V$ of nodes ...
1
vote
0answers
391 views

Best algorithm to generate matchmaking pairs

I am trying to come up with a matchmaking algorithm based on player ratings for my game, and I am pretty sure the algorithm I have is not the best (or maybe doesn't even work), but have no idea how to ...
1
vote
0answers
490 views

Optimal Preference Matching

I'm trying to find an algorithm that finds an optimal matching between $A$ and $B$, where each element $a$ of $A$ provides a preference order $\prec_a$ over $B$. I will notate the index of an element $...
1
vote
0answers
200 views

Matching odd-degree nodes in an undirected graph

The Chinese Postman problem (A.K.A Route Inspection Problem) I'm trying to match pairs of odd-degree nodes in a grid-graph representing an indoor map to ensure the graph is Eulerian (consists only of ...
1
vote
0answers
27 views

Maximal Matching of nodes that fall into four categories

Nodes have values. Node n's value is denoted n.val. Two or more nodes can have the same value. A node ...
1
vote
0answers
390 views

approximation algorithm of k-set packing

For my application problem, I am looking for an easy to implement or source code for approximation algorithm for maximum k-Set Packing problem. Given a universe $U$ and a family $ \mathcal{S} $ of ...
1
vote
0answers
83 views

Matching elements of two sequences: choosing the best one

I have the following problem. Let $P$ and $Q$ be two ordered sequences of time instants. $[p_0,p_1,\ldots,p_n]$ and $[q_0,q_1,\ldots,q_m]$ are the elements of $P$ and $Q$ respectively. A first ...
1
vote
0answers
89 views

Using A* to find the word closest to an input rejected by a finite automaton

In the article Fast approximate string matching with finite automata by M. Hulden (2009) (mostly pages 58/59), the author describes how to search for a closest matching string word from an automaton ...
0
votes
0answers
19 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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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, ...
0
votes
0answers
43 views

Options for approaching stable marriage problem with unequally sized sets of elements/preferences

I am looking for an algorithm/code that will provide stable matching for two unequally sized sets of elements (clubs and students) with an unequal set of preferences. There is a large pool of students ...
0
votes
0answers
17 views

Relation between shape descriptors and featured connected component in matching problems

Hope I'm asking in the correct community, from the title, I need a clarification regarding the idea of dealing with 3d descriptor and featured connected components. I have this approach: model -> ...
0
votes
0answers
140 views

Maximum matching blossom algorithm

https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf Why do we use blossom contrast in maximum matching? The examples that I have seen can easily be solved by just ...
0
votes
0answers
41 views

Find maximal matching in tree in $O\left(\frac{n}{\log n}\right)$

As any tree can be described as a binary sequence ($i$-th bit is 0 if the edge goes down and 1 otherwise, every edge is travelled twice $-$ up and down, so such sequence's length is $2 |V| - 2$), any ...
0
votes
0answers
57 views

Hopcroft und Karp Algorithm and a suitable representation for a graph

Hey Guys I have a small question about the Hopcroft and Karp Algorithm. I have a task to solve where I have to calculate the perfect matching. My professor told me I should use the Hopcroft Algorithm....
0
votes
0answers
23 views

Is implementation of approximate dynamic maximal matching feasible?

I'm wondering if algorithms described in: https://ieeexplore.ieee.org/abstract/document/7782946/ http://drops.dagstuhl.de/opus/volltexte/2014/4845/ easy to implement. They seem to mention the word "...
0
votes
0answers
173 views

Edge incident to cut-vertex not in perfect matching of a graph

Let G = (V,E) be a connected graph and a ∈ V be an articulation point of G. How can be proved that there is an edge e ∈ G incident with a with the property that e doesn't belong to a perfect matching ...
0
votes
0answers
799 views

Minimum cost perfect matching (Using General graph

This is a continuation of the problem described in this topic: Optimized algorithm to match entities together based on heuristics. I've come a little closer as to what might be the best solution. I'...
0
votes
0answers
116 views

Distributed Algorithm for Minimum Cost Maximum Matching in General Graphs

What are the fastest distributed algorithms for minimum cost maximum matching in general graphs? I found two papers that talk about approximation algorithms but I want algorithms that solve the ...
0
votes
0answers
20 views

Problem with Blossoms while searching for augmenting pathes

I have problems understanding the effect of Blossoms while searching for augmenting pathes (in the matching problem). If I have the following graph Can't I find the augmented path from n1 to n13? ...
0
votes
0answers
26 views

How do I show that the matching polytope of $K_{2n}$ is a linear projection of the perfect matching polytope of $K_n$?

Of course a matching polytope is the convex hull of edges in a matching and similarly for a perfect matching polytope.
0
votes
0answers
51 views

Effect of mismatches on string matching finite automata

I am contemplating a string matching FA algorithm (not KMP). The complexity of its transition function calculation ie the preprocessing is m(length of pattern )* (the language of the FA) . What effect ...
-1
votes
1answer
14 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|$?
-1
votes
1answer
34 views

Best and Worst options in Gale Shapley algorithm for an agent

Please consider the figure below. I have to find the best and worst options for W. From the preference list of W, the best option for W is D but there is no matching of W with D in all the 6 options. ...
-1
votes
1answer
356 views

Definition of valid partner in Stable Matching Problem

From Tardos and Kleinberg's Algorithm Design, the definition for "worse valid partner" is basically — $m$ is $w$'s worse valid partner if $m$ is a valid partner of $w$, and no man whom $w$ ranks ...