Skip to main content

All Questions

Filter by
Sorted by
Tagged with
0 votes
1 answer
77 views

Bipartite matching where every adjacent pair of vertex on the left side of the graph has at least 1 vertex matched

The question is as stated above. I want to devise bipartite matching algorithm where it determies whether every adjacent pair of vertex on the left side of the bipartite graph has at least 1 vertex ...
MHC_Class_2's user avatar
2 votes
1 answer
315 views

Bipartite matching with a pairwise constraint

A long time ago I remember seeing a very clever construction for the following problem, but I can't find a reference for it anywhere: suppose I have a bipartite graph $G=(U\cup V, E)$, and the ...
Tom Solberg's user avatar
  • 4,049
4 votes
0 answers
118 views

Reorganizational matching

Motivation. My friend works in an organization that is re-organizing itself in the following somewhat laborious way: There are $n$ people currently sitting on $n$ jobs in total (everyone has one job). ...
Dominic van der Zypen's user avatar
2 votes
0 answers
163 views

Generalizing Hall's marriage theorem to non-perfect matchings

Let $G = (X, Y, E)$ be bipartite graph such that $|X|=|Y|=n$. A matching $M \subseteq E$ is a subset of disjoint edges (i.e., there does not exist a pair of edges $(x, y) \in M$ and $(x', y') \in M$ ...
errorist's user avatar
  • 121
5 votes
1 answer
1k views

Bipartite graph with exactly one perfect matching

$\textbf{Problem:}$ Find all bipartite graphs $G[X,Y]$ satisfying the following properties: $1.$ $|X|=|Y|$, where $|X|\ge 2$ and $|Y|\ge 2$. $2.$ All vertices have degree three except for two vertices ...
Sanket Biswas's user avatar
1 vote
1 answer
312 views

Unique bipartite perfect matchings and cycles?

Given a graph $G$ which is bipartite and balanced and has unique perfect matching let $G^{e}$ be $G$ without edge $e$. Let $G\cup G_{\pi,\pi'}$ be union of $G$ and $G_{\pi,\pi'}$ where $G_{\pi,\pi'}$ ...
Turbo's user avatar
  • 13.9k
2 votes
2 answers
223 views

Number of subgraphs with matching of size $n$ for a complete bipartite graph

Say we have a $K_{n,n}$ bipartite graph (i.e. a complete bipartite graph with $n$ nodes on each side). We induce a subgraph by deleting some subset of edges. There are $2^{n^2}$ possible subgraphs. ...
TPaul's user avatar
  • 41
7 votes
1 answer
969 views

Graph to Bipartite conversion preserving number of perfect matchings

Given a graph $G$ on $n$ vertices is there a technique to convert to a balanced bipartite graph $B$ with $O(n^c)$ vertices at some fixed $0<c$ in $O(n^{c'})$ time at some fixed $0<c'$ such that ...
Turbo's user avatar
  • 13.9k
4 votes
2 answers
985 views

Applications of Hafnians

I am learning about Hafnians but I am struggling to find real-world applications of them. I understand the applications of determinants, permanents, and even pfaffians but I am at a loss for Hafnians. ...
Aidan Kehoe's user avatar
-1 votes
1 answer
378 views

Marriages in infinite bipartite graphs with many neighbors

Let $A,B\neq \emptyset$ be disjoint and suppose $G = (A\cup B, E)$ is bipartite where for all $e\in E$ we have $e\cap A \neq \emptyset\neq e\cap B$. For $a\in A$ we set $N_G(a) = \{b\in B: (\exists e\...
Dominic van der Zypen's user avatar
5 votes
2 answers
4k views

Solving assignment problem using Hungarian method vs min cost max flow problem

The traditional solution for the assignment problem is the Hungarian method - it's complexity is O(V^4) or O(V^3) if using Edmonds method. However, it can also be reduced to a min cost max flow ...
EugeneMi's user avatar
  • 201
4 votes
1 answer
1k views

Polygamous stable marriage/ assignment problem

I'm not sure under which 'algorithm' it falls under, but here is the problem: I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...
EugeneMi's user avatar
  • 201
6 votes
2 answers
7k views

How many perfect matchings in a regular bipartite graph?

We have a $d$-regular bipartite graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$. What is an upper bound on the number of perfect matchings of $G$?
pnaky's user avatar
  • 61
0 votes
1 answer
773 views

Counting matchings in a bipartite matching-covered graph

A graph is called matching-covered if every edge is containd in a perfect matching. (Such graphs are also sometimes called "elementary", e.g. in Chapter 4 of "Matching Theory" by Lovasz & Plummer)....
Felix Goldberg's user avatar
4 votes
0 answers
207 views

Bounds on numbers of matchings of given sizes in bipartite graphs

I am interested in the following question: For which sets ${m_1,\ldots m_k}$ of positive integers do there exist bipartite graphs having exactly $m_i$ matchings of size $i$ for each $1\leq i \leq k$, ...
Adam 's user avatar
  • 1,327
13 votes
2 answers
811 views

Gale-Shapley stable marriage theorem: can we entrust matchmaking to monkeys?

Disclaimer: This is a question I have not done any real research about. I asked it myself some 5 years ago, and back then I had no idea where to start. Now I have some texts on stable matchings lying ...
darij grinberg's user avatar
8 votes
1 answer
2k views

Condition on a bipartite graph to have an $m$-factor

This might be the most stupid question I am ever posting here: I am asking for a proof or a counterexample to a problem I proposed on MathLinks long ago. Let $G$ be a bipartite graph, i. e., a graph ...
darij grinberg's user avatar