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.
218
questions
3
votes
0
answers
59
views
Lights-out! on a hex grid with buttons on nodes and lights on faces
Consider a truncated hexagonal grid, with some hexagons lit up, such as the one shown below:
Here the red hexagons are lit up while the dark gray hexagons are not lit up. The grid has buttons (small ...
- 5,772
2
votes
1
answer
48
views
For a regular bipartite graph with vertices $X\cup Y$, prove that $|S|\leq|n(S)|$ $\forall S\subseteq X$
As the title states, we are given a bipartite undirected graph $G=(X\cup Y,E)$ such that every vertex $v\in V$ satisfies $d(v)=k$ for a constant $k$.
The general goal of the proof is to show that ...
- 293
1
vote
1
answer
30
views
Assign items from inventory to people maxmizing the number of satisfied people
We have a set of people, and each person has a list of wished items (not unique, they could want multiple copies of each item). We have an inventory of items that we want to assign to the people. We ...
- 111
0
votes
1
answer
27
views
Choosing root for maximum matching in tree
This question deals with how to find the maximum matching in a tree. I understood the answers, but for one part.
Choose a root arbitrarily. For each subtree, calculate the maximum matching within the ...
- 121
0
votes
0
answers
20
views
Analyzing Parallel Matching Algorithm - Why it takes O(n+m) time and work?
Using the algorithm provided by this paper, they said that:
The algorithm defines a single phase of the local max algorithm. Each step of the phase takes at most O(log(m + n)) = O(logn) time and O(n +...
0
votes
0
answers
20
views
How does parallel marching algorithm work?
For the following graph and graph representation:
V set: An array of n elements, where each entry V[i] = Pj<i deg(vj).
A set: An adjacency array representation of a graph, where entries A[V[i]] ...
- 1
0
votes
1
answer
19
views
What is the associative operator ⊕ in graph matching? and How does it works?
I read a paper about Parallel Matching, and I didn't understand what the associative operator ⊕ in the following lemma/proof and how does it works in vertices and edges in the graph?
Lemma 3. Using ...
- 1
0
votes
0
answers
33
views
How to assign people to take part in an activity with limited space, with some people having priority over others
I am trying to solve a seemingly straightforward problem, for which a well-known algorithm should exist, but I can't find it.
Imagine we have an activity, let's say football/soccer. Obviously, only 11 ...
- 101
1
vote
1
answer
36
views
How to argue that an $A$-covering matching exists in this bipartite graph?
In lecture the following was mentioned in the context of matchings in bipartite graphs:
Let $U$ be a finite set and let $\mathcal{S}$ be a family of subsets of $U$.
For $u \in U$ let $r(u) := \lvert \...
- 457
1
vote
2
answers
81
views
Matching students with companies based on their preference
I have a list of companies with n timeslots (number of slots may vary from company to company) and a list of students. Each student made a list of their top 3 companies they would like to talk to.
Is ...
- 11
1
vote
0
answers
40
views
Understanding how the total # of comparisons is derived for the worst case in the "Brute-Force String Matching" algorithm
The Total number of comparisons for the worst case in the "Brute-Force String Matching" algorithm is: (n-m+1) where ...
- 13
0
votes
1
answer
29
views
Proving that this matching is stable
Consider the stable marriage problem with $n$ men and $n$ women. Let $A$ and $B$ be two stable matchings, and suppose that we form a new matching $C$ by assigning to each men his favorite partner ...
- 247
0
votes
0
answers
16
views
Comparing two poses of a point cloud
I have an unstructured point cloud for which I determine pose information described as a similarity transform (rotation matrix and translation vector). In my setting, several independent poses are ...
- 7,141
1
vote
1
answer
47
views
Max matching algorithm lemma approximation algorithm
We have this algorithm which is supposed to find max matchings.
...
- 37
2
votes
1
answer
86
views
Proving that the number of leaves in a tree >= number of unmatched vertices
Consider a rooted tree $T$. A matching in $T$ is said to be proper if for every unmatched vertex $v$ it holds that the parent of $v$ is matched to one of the siblings of $v$. It is known that every ...
- 391
1
vote
1
answer
98
views
Is Set Cover problem with subsets of size ≤2 solvable in polynomial time?
I came across the below question where the polynomial time solution to the "Set Cover Problem" is discussed when the subsets are of size EXACTLY 2.
Set cover problem with sets of size 2
The ...
2
votes
2
answers
47
views
Matching problem in bipartite network with more than one edge per vertex
I'm interested to know if there is an algorithm to find possible solutions for the matching problem, in a bipartite network where each vertex have maximum number of connections greater than one. For ...
- 133
1
vote
1
answer
43
views
Find a perfect matching with weights as close as possible to each other
Given a set of jobs $J$ and a set of machines $M$, where the link between machine $i\in M$ and job $j\in J$ has a positive weight $w_{ij}$. The problem is to select a perfect matching between the jobs ...
- 1,026
2
votes
1
answer
30
views
Using algorithm for weighted graphs when the weights are vectors
Consider the following example problem. Given a graph with edge weights, find a matching that maximizes the number of matched vertices, and subject to this, maximizes the total weight. This problem ...
- 5,768
2
votes
0
answers
35
views
Proving existence of sinkless orientation on graph with minimum degree 2
I am given a graph of minimum degree at least 2 (not necessairly regular). I want to prove that there is a way to orient the edges of G such that each node of G has at least one out-going edge.
As a ...
- 149
0
votes
1
answer
46
views
Prove there is a matching of size n/2 on a graph with 2n vertices each of degree n
Given underirected $n$-regular graph with $2n$ nodes, I am asked to show it has a matching of size $n/2$.
My attempt:
At each step I will also remove the edge from the graph that I am adding to the ...
- 149
0
votes
1
answer
121
views
Find a maximum matching in linear time - How to prove it?
Let B be an undirected tree with |V| nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime O(|V|).
I understand that the solution ...
1
vote
1
answer
73
views
Max-Min Weighted Matching
The maximum weighted matching problem (https://en.wikipedia.org/wiki/Maximum_weight_matching) finds a matching in a weighted graph that has maximum sum of weights. I was wondering if there are any ...
- 25
1
vote
0
answers
146
views
Graph in which greedy algorithm for maximum matching is a 2-approximation
Here is a greedy algorithm for maximum bipartite matching:
Iteratively select an edge that is not incident to previously selected edges.
This algorithm returns a 2-approximation, and runs in linear ...
- 111
5
votes
1
answer
71
views
The maximum matching of a bipartite graph $(S, T)$ is $|X|+\min\limits_{A \subseteq X} (\min\{0, |N_G(A)|-|A|\}$, where $X \in \{S, T\}$?
Here is the full version of the problem I'm dealing with.
Let $G=(S,T;E)$ be a bipartite graph and let $X$ be one of the two classes of its bipartition (i.e., $X \in \{S,T\}$). For a subset $C \...
- 75
2
votes
0
answers
49
views
Size of the maximum matching in arbitrary graph
I am asked to find a probabilistic algorithm to determine the size of the maximum matching of an arbitrary simple undirected graph $ G $.
My claim is that, it is equivalent to find a global min cut on ...
- 149
1
vote
1
answer
497
views
How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time
This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani.
Specifically, the problem statement is:
Give a linear-time algorithm that ...
- 235
1
vote
1
answer
706
views
How can we express value of cosine similarity of two documents into percentage?
We were doing project work for plagiarism checking. For this purpose, we have taken a term frequency vector of two documents and measured the similarity using a cosine similarity measure. The value of ...
- 27
10
votes
0
answers
78
views
Maximum matching with social distancing
Let $G = (X\cup Y, E)$ be a bipartite graph. Suppose $X$ contains people, $Y$ contains seats in a theatre, and each edge $(x,y)$ has a weight representing how much person $x$ is willing to pay for ...
- 5,768
4
votes
1
answer
141
views
Maximum-weight matching with a bounded number of fractional edges
In graphs with odd cycles, the maximum weight of a fractional matching may be higher than that of a standard matching. For example, in a cycle of length 3, where all edges have weight 1, the maximum-...
- 5,768
0
votes
1
answer
74
views
Algorithm best compare similarities between two data sets in percentage
I'm trying to create an algorithm that finds the percentage of similarity between two subjects with sets of survey questions.
Example:
Q1: Do you prefer physically demanding tasks?
A1: Nope Maybe Yes -...
- 101
1
vote
0
answers
71
views
Hardness result for online matching
Currently studying the following paper:
"Fair Allocation in Online Markets" - Gollapudi and Panigrahi 2014
In which they present Theorem 2 as a hardness result for online maxmin matchings (...
- 11
5
votes
2
answers
145
views
How to match two point sets to minimize total distance?
Let's say we have two sets $X = \{x_1, \ldots, x_n\} \subset \mathbb R^d$, $Y =\{y_1,\ldots, y_n\} \subset \mathbb R^d$, how can we find a permutation $\pi$ such that
$$D = \sum_{i=1}^n d(x_i, y_{\pi(...
- 373
1
vote
1
answer
53
views
Three dimensional matching expressed as SAT
The posting in the website Embedding SATISFIABILITY into 3-DIMENSIONAL MATCHING seeks $3SAT$ as a $3$ dimensional matching instance.
I am looking to solve the converse problem. How to solve three ...
- 2,834
1
vote
1
answer
107
views
Algo to match students to universities (only students choose & rank)
I'm trying to develop an algorithm in Ruby to allocate one university to each student of a list. As opposed to Gale-Shapley algorithm, universities do no choose nor rank students; only students make a ...
- 11
1
vote
1
answer
63
views
What is the comparator circuit?
The standard circuits $AC^i$, $NC^i$ are constructed using $AND$, $OR$ and $NOT$ of various fan-ins, fan-outs and depths.
What is the comparator gate constituted from?
Structurally why is it believed $...
- 2,834
0
votes
0
answers
23
views
What is the depth of comparator circuit required in Gale Shapely and STCONN?
Stable matching problem and $STCONN$ can be solved using comparator circuits (refer https://arxiv.org/abs/1208.2721).
What is the depth of the $CC$ circuit necessary for stable matching? Is it in $CC^...
- 2,834
2
votes
0
answers
25
views
Subgraph isomorphism index/precomputation
I'm currently working on problem in which a set of graphs $T=\{t_1,\dots,t_n\}$ is given and fixed.
Given a graph $m$ I want to check which of the $t_i$ are subgraphs of it, as quick as possible.
Is ...
- 121
1
vote
0
answers
52
views
Hardness of multiplicative vs. additive approximation
Chlebik and Chlebikova prove that the problem "maximum 3-dimensional matching" is NP-hard to approximate within a multiplicative factor of $95/94$.
This means that, unless $P=NP$, there is ...
- 5,768
1
vote
1
answer
60
views
a lower bound for the maximum fraction of matchings not containing an edge
I am trying to prove the following statement (from book, page 317):
Let $G(A,B,E)$ be a bipartite graph, where $A$ and $B$ are the two disjoint sets of vertices s.t. $|A|=|B|=n$. Let the number of ...
- 2,891
0
votes
1
answer
30
views
Match unpaired points between two sets
I have two sets, let's call them C and T, of unpaired points, which could for example represent two types of cells. Hence, both points are drawn from the same underlying distribution, but the points ...
- 133
1
vote
1
answer
377
views
Finding preferences for G-S algorithm (Algorithm Design Chapter 1 exercise 7)
I'm working on Algorithm Design (Kleinberg-Tardos) Chapter 1 exercise 7:
Some of your friends are working for CluNet, a builder of large
communication networks, and they are looking at algorithms for
...
- 157
0
votes
1
answer
68
views
How are matchings a lower bound for an approximate vertex cover?
I am reading Algorithms by Dasgupta et al and they mention maximal matchings as approximations for vertex cover.
They mention that the 2-approximation ratio is a lower bound. How is a maximal matching ...
- 659
1
vote
0
answers
66
views
Disjoint groups using maximum matching
In the 3-Path Packing problem, we are given an undirected graph $G$ and a parameter
$k \in \mathbb{N} \cup \{0\}$. We need to answer Yes/No if there exists a collection of $k$ vertex disjoint paths on ...
- 203
4
votes
0
answers
70
views
Find an optimal matching in a complete graph
I have a complete edge-weighted graph with $n$ vertices (and therefore $n\cdot(n-1)/2$ edges). I want to find a complete matching (i.e., perfect matching) in which the quotient $sum_G/A_G$ is maximal, ...
- 41
0
votes
0
answers
31
views
Stochastic matching with fewer queries
Given a graph $G = (V,E)$ and a probability $p \in [0,1]$ with which each edge is sampled from the graph $G$. The goal of the stochastic matching problem with fewer queries is to find a subgraph $H \...
- 1
2
votes
2
answers
255
views
Maximum weight perfect matching in general graphs
Let $G(V,E)$ be a graph (not necessarily bipartite), where edge $e \in E$ has weight $w_e$ (non-negative real). Then one can write the LP relaxation for maximum weight perfect matching as follows
$$
\...
- 2,891
1
vote
0
answers
75
views
Can somebody please explain what are these variables doing here?
I have this algorithm:
I understand overall what's happening here, we're shrinking the blossoms (odd cycles) to end up with a bipartite matching problem, and then opening them again to get a maximum ...
- 121
2
votes
1
answer
326
views
calculating the string similarity of an optimal alignment
description of the algorithms behavior
I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the ...
- 71
0
votes
0
answers
53
views
Is there an approximation algorithm for the three-person stable roommates problem?
While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the "threesome roommates problem", ...
- 101