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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
13 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 ...
user avatar
  • 4,537
1 vote
1 answer
28 views

Max matching algorithm lemma approximation algorithm

We have this algorithm which is supposed to find max matchings. ...
user avatar
  • 37
2 votes
1 answer
81 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 ...
user avatar
1 vote
1 answer
59 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 ...
user avatar
2 votes
2 answers
34 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 ...
user avatar
  • 123
1 vote
1 answer
42 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 ...
user avatar
  • 1,016
2 votes
1 answer
23 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 ...
user avatar
2 votes
0 answers
27 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 ...
user avatar
  • 149
0 votes
1 answer
41 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 ...
user avatar
  • 149
0 votes
1 answer
71 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 ...
user avatar
1 vote
1 answer
26 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 ...
user avatar
  • 25
1 vote
0 answers
95 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 ...
user avatar
  • 111
5 votes
1 answer
64 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 \...
user avatar
  • 75
2 votes
0 answers
38 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 ...
user avatar
  • 149
1 vote
1 answer
341 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 ...
user avatar
1 vote
1 answer
387 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 ...
user avatar
10 votes
0 answers
69 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 ...
user avatar
4 votes
1 answer
128 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-...
user avatar
0 votes
1 answer
37 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 -...
user avatar
1 vote
0 answers
70 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 (...
user avatar
4 votes
2 answers
93 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(...
user avatar
  • 363
1 vote
1 answer
35 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 ...
user avatar
  • 2,824
1 vote
1 answer
59 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 ...
user avatar
  • 11
1 vote
1 answer
59 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 $...
user avatar
  • 2,824
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^...
user avatar
  • 2,824
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 ...
user avatar
1 vote
0 answers
43 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 ...
user avatar
1 vote
1 answer
54 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 ...
user avatar
0 votes
1 answer
29 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 ...
user avatar
  • 133
1 vote
1 answer
355 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 ...
user avatar
0 votes
1 answer
53 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 ...
user avatar
1 vote
0 answers
65 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 ...
user avatar
  • 103
4 votes
0 answers
56 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, ...
user avatar
  • 41
0 votes
0 answers
30 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 \...
user avatar
2 votes
2 answers
203 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 $$ \...
user avatar
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 ...
user avatar
  • 121
2 votes
1 answer
279 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 ...
user avatar
0 votes
0 answers
44 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", ...
user avatar
  • 101
0 votes
1 answer
28 views

Matching with specific cardinality

In a weighted graph $G(\mathcal{V},\mathcal{E})$ where $w(i,j)$ is the weight of the edge $(i,j) \in \mathcal{E}$. How can I find a maximum weighted matching with a specific size (i.e specific ...
user avatar
  • 131
0 votes
0 answers
65 views

Computing a fractional matching of maximum product in a bipartite graph

Given a bipartite graph $(X\cup Y, E)$ with edge weights, it is easy to find a matching in which the product of weights is maximum: replace each edge weight with its logarithm, and find a matching in ...
user avatar
1 vote
2 answers
105 views

Maximum matching for general graph

I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must ...
user avatar
  • 111
1 vote
1 answer
427 views

Can't wrap my head around on building a suffix table for Boyer Moore

My resources were the following video, as well as this video. Basically, in one of the videos they state that the good suffix table for the pattern "ABCBAB" is the following: k suffix d2 1 ...
user avatar
  • 113
2 votes
1 answer
129 views

maximum cardinality weighted matching

I am looking for a reference for maximum cardinality weighted matching and the best running time algorithm for it. Maximum Cardinality Weighted Matching: Given an undirected weighted graph $G(\mathcal{...
user avatar
  • 131
2 votes
1 answer
226 views

Find optimal local alignment of two strings with restrictions

I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it. The problem: We want to find an optimal local ...
user avatar
  • 165
1 vote
1 answer
45 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 ...
user avatar
1 vote
1 answer
36 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 ...
user avatar
4 votes
2 answers
73 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 ...
user avatar
  • 43
3 votes
1 answer
195 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 ...
user avatar
  • 137
-1 votes
1 answer
63 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|$?
user avatar
  • 99
1 vote
1 answer
50 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$?
user avatar
  • 137

1
2 3 4 5