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.

learn more… | top users | synonyms

0
votes
0answers
20 views

Is maximum size of graph matching equal to maximum size of its dual graph matching?

This is really puzzling me! A hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$. A ...
2
votes
2answers
90 views

Finding perfect matchings with as few database queries as possible

I am trying to research a problem similar to the stable matching problem with a few different rules. The problem is as follows: There are an equal number of men and women. Each man has a perfect ...
2
votes
1answer
46 views

Equality of cardinality of maximum matching and minimum vertex cover in general

I'm preparing for exam and I came across this problem: We say that a graph is König's graph when the sizes of its minimum vertex cover and maximum matching are equal. Find a polynomial time ...
3
votes
0answers
11 views

Set of vertex-disjoint cycles maximizing different colored vertices

Let $G=(V,E)$ be a directed graph whose vertices $v \in V$ have colors and its edges $e\in E$ have costs $cost(e)$. I am looking to find a set of vertex-disjoint cycles that: First maximizes the ...
0
votes
0answers
22 views

Algorithm for assignment of workers to non-overlapping subsets

I am curious if there is an efficient solution to the following variant of the linear sum assignment. For example, can it be modelled as a matching problem or linear program? I have a finite quantity ...
3
votes
1answer
21 views

Woman optimal Gale Shapley Stable Matching

I am learning about Gale Shapley Algorithm now, and I understand that it is Man Optimal and that all possible executions will yield a stable matching where each man gets the best partner that he can ...
1
vote
1answer
35 views

A condition ensuring that a bipartite graph have a perfect matching

There is a bipartite graph $G=(A,B,E)$ such that for every edge $(a,b)$ (where $a$ comes from $A$ and $b$ from $B$), $\deg(a) \geq \deg(b)$, and additionally $\deg(a) \geq 1$ for all $a \in A$. From ...
3
votes
0answers
51 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
votes
1answer
46 views

Is the maximum matching problem trivial when the graph is complete?

I have a quick question. The maximum matching problem is an easy problem but not a trivial one. I was wondering that if the bipartite graph was complete, is it a trivial problem? I think we can just ...
2
votes
0answers
88 views

Vertex-disjoint cycles passing through a collection of vertices

I am wondering about the complexity of the following problem: given a directed graph $G=(V,E)$ (which may have self-loops at some vertices) and a subset of the vertices $U \subset V$, does there exist ...
0
votes
0answers
16 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.
2
votes
1answer
634 views

Perfect matching in a graph and complete matching in bipartite graph

When I google for complete matching, first link points to perfect matching on wolfram. It defines perfect matching as follows: A perfect matching of a graph is a matching (i.e., an independent ...
3
votes
1answer
94 views

Why is Savage's Vertex Cover algorithm a 2-approximation?

Carla. D. Savage formulated the following approximation algorithm for the vertex cover problem. Given graph $G$, start at arbitrary node and traverse $G$ depth-first Obtain DFS tree $T$ ...
3
votes
0answers
122 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). ...
1
vote
1answer
93 views

Assignment based on ranked preference

Assume that there are n students, who have to be evenly assigned to m groups. For every student, a preference ranking of of the <...
1
vote
1answer
71 views

Bit-parallelism and NFA simulation

In several papers I have read that Bit-parallel pattern matching is an NFA-simulation. My questions are: 1- Is it true in general? Or, is there any restrictions? 2- As any regular expression can be ...
9
votes
0answers
182 views

How fast can we compute the size of maximum matching in an unweighted bipartite graph?

Is there a way to compute the size of a maximum matching in an unweighted bipartite graph more efficiently (e.g. faster) than computing a maximum matching? It is a long shot but it is often ...
2
votes
1answer
55 views

Computing optimal assignments using little memory

I have two lists where each item in the first list has a rating for each item in the second. I need to determine an optimal matching (or the best x scenarios) where items are matched, but each item ...
1
vote
0answers
61 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
2answers
79 views

NFA-style representation of regexps which includes AND

I'm looking for a regexp matching strategy that supports conjunction and which is based on an NFA-style machine. I know how to handle conjunctions using a DFA, or using Brzozowski's approach, but for ...
0
votes
0answers
22 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
vote
1answer
48 views

Similarity of two monochromatic shapes

I need to find out to what extent two shapes are similar. I mean I've got two vectors of points - and just that, no shadows, color or whatever - simplest case. Two triangles are the perfect example. ...
2
votes
1answer
28 views

About having analytic control over any algorithm which finds perfect matchings.

A trivial algorithm to decompose a degree-d (n,n)-bipartite graph into d disjoint perfect matchings is this : direct all the edges from left to right and put capacity one on each of them - then add a ...
3
votes
1answer
920 views

Find perfect matching whose weight is minimal, in polynomial time

Given a bipartite graph $G=(A,B,E)$ and a weight function $w: E \rightarrow\mathbb{R}^+$, I'd like to find a perfect matching $M\subseteq E$ with min. weight. I'm assuming $|A| \leq |B|$, and WLOG $G$ ...
0
votes
1answer
367 views

Gale–Shapley algorithm is man-optimal

I am trying to understand the proof why Gale–Shapley algorithm is optimal, however i am unable to do so. Could you please expand the proof, since the proof on this page https://sites.google.com/site/...
1
vote
1answer
260 views

How to do high performance string matching when comparing unordered sets of tokens [closed]

This is the problem: I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one ...
-1
votes
1answer
47 views

Stable marriage problem with more people then priorizations [closed]

I am trying to solve a stable marriage problem where I have e.g. 20 women and 20 men, but they always only prioritise 4 pre-selected people of the opposite sex. My algorithm distributes all men and ...
1
vote
0answers
58 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 ...
2
votes
1answer
622 views

Stable marriage problem with only one side having preferences [duplicate]

I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and ...
2
votes
1answer
59 views

Could an alternating approach yield a fairer solution to the stable marriage problem?

With the G-S algorithm solution to the stable marriage problem, the proposers get the best possible stable matches, while the reviewers get the worst possible stable matches. This is because the ...
5
votes
1answer
93 views

Finding a perfect matching using an LP

I have a basic question about the power of Linear Programming that has been bothering me for some time. I believe there is something simple I am missing. Linear Programming is $\mathsf{P}$-complete, ...
1
vote
0answers
131 views

Finding the number of distinct maximal matching in a bipartite graph [closed]

In a bipartite graph, how can we find the total number of ways of getting a maximal matching? The cardinality of both the sets in the bipartite graph may not be the same. So two matchings are said to ...
0
votes
1answer
76 views

Algorithm for distributing members over activites (with individual preferences)

So in my school we have a day where everybody participates in different activities. Each projects can have like 10 members. The whole day is divided in 2 or 3 different blocks, in which the pupils ...
6
votes
1answer
302 views

Complexity of Hopcroft-Karp

I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where ...
1
vote
2answers
146 views

Algorithm to match timestamped events from two sources

does a good known algorithm exists for this problem? On input I have two series of timestamps "when the event was observed". Theoretically the recorded timestamps should be very well aligned. ...
1
vote
1answer
349 views

Why can't we solve the dinner party problem by finding a maximum matching?

Consider the following dinner party problem: Given a list of acquaintances, and a list containing all pairs of individuals who are not on speaking terms with each other, find the largest set of ...
0
votes
3answers
117 views

Bipartite Matching in the Plane

I'm currently working on a problem that I came across: You are given a set $B$ of $n$ points in the plane, and a set $R$ of $n$ points in the plane. Each point is given by its coordinates. I have ...
5
votes
1answer
476 views

How are REGEXP implemented in programming languages?

Is there a good general paper about the interpretation or compilation of REGEXP in programming languages for pattern matching, with or without variables? I am not looking for a quick explanation about ...
1
vote
1answer
79 views

Are algorithms for searching text vs searching numbers fundamentally different?

I face this problem a lot while searching phone numbers and bank account numbers, when I do remember it partially. I save a draft in gmail with the content ...
4
votes
2answers
250 views

How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this?

Suppose that I have a set of $N$ points in $k$-dimensional space ($k>1$), such as in this question, and that I need to find all pairs with a distance¹ smaller than a certain threshold $t$. The ...
3
votes
0answers
63 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 ...
2
votes
1answer
193 views

Degree conditions sufficient for Hall's theorem

Let $G=(L,R,E)$ be a bipartite graph, are there conditions on the degree of the vertices under which the condition of Hall's theorem is surely satisfied? (meaning a perfect matching exists in the ...
2
votes
1answer
87 views

What's the dual problem of stable matching?

So the dual problem of max-flow is min-cut. What's the dual problem of stable matching?
4
votes
1answer
2k views

Counting and finding all perfect/maximum matchings in general graphs

Recently i've been dealing with a problem that led me to the following questions: Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph? Is there a good algorithm ...
2
votes
1answer
77 views

Number of Matchings in a Bipartite

Given two sets A and B of sizes |A| = n and |B| = m, where m >= n. There are edges from set A to set B. I need to find the number of matchings where all of vertices ...
2
votes
2answers
907 views

Confusion about finite automata construction in Knuth–Morris–Pratt algorithm

There is one point I don't understand in the DFA construction for mismatch cases. Here is the lecture note I watched, which describes how to handle mismatched characters during the DFA construction ...
0
votes
1answer
169 views

Is there a formula to state the number of 'sets' of 'ordered sets within ordered groups'?

I am new to this and an amateur... please help. My Question in practical terms: Given The three following inputs... determine the number of unique group arrangements as an ordered set. INPUT: 'a' = ...
2
votes
0answers
76 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 ...
11
votes
1answer
366 views

Sampling perfect matching uniformly at random

Suppose I have a graph $G$ with $M(G)$ the (unknown) set of perfect matchings of $G$. Suppose this set is non-empty, then how difficult is it to sample uniformly at random from $M(G)$? What if I am ...