All Questions
Tagged with matching-theory graph-theory
128 questions
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 ...
- 126
0
votes
0
answers
42
views
How to determine if two matchings are related by a permutation?
Let $n \geq 2$ be an integer. Let
\begin{align*}
V &= \{(i, j); 1 \leq i, j \leq n \text{ and } i \neq j \} \\
E &= \{ \{v_1, v_2\}; v_1, v_2 \in V \text{ and } v_1 \neq v_2 \}.
\end{align*}
...
- 5,215
4
votes
2
answers
381
views
Max weighted matching where edge weight depends on the matching
Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other ...
CommunityBot
- 1
1
vote
1
answer
97
views
Algorithmic complexity of calculating maximum weight $k$-regular subgraphs
Question:
what is known about the complexity of calculating the heaviest $k$-regular subgraph of a weighted symmetric graph if edge-weights can also be negative?
Please note that in contrast to $k$-...
CommunityBot
- 1
1
vote
0
answers
48
views
How to solve a optimal matching problem where the "quality" of matching is only determined once all nodes are matched
Note: I'm not a mathematician; I'm just a biologist with basic math background trying to solve a scientific problem, so please excuse my ignorance.
The gist of the problem is as follows:
I have two ...
- 5,429
7
votes
3
answers
393
views
Perfect matchings of a regular, uniform, partite hypergraph
This is in relation to the question here. What, if any, are the known conditions for the existence of a perfect matching for a $r$-regular, $r$-uniform, $r$-partite hypergraph. I specifically ...
- 221
3
votes
1
answer
140
views
Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs
It is well known that for a bipartite graph $G$ with bi-adjacency matrix $A$, then $\det A \neq 0$ (as a polynomial) iff $G$ has a perfect matching (there is a similar result for general graphs with ...
- 18.8k
1
vote
1
answer
54
views
Complexity of maximum weight-sum matching for cycle graphs
I need to determine a matching with maximal weight-sum for a cycle graph with positive, negative and zero edge-weights.
Question:
What is the fastest way of calculating such a matching?
Because of ...
- 13.2k
14
votes
2
answers
481
views
Number of matchings of even cycles
By doing some calculations on the generating function of matching polynomials of cycles I made the following interesting observation:
For all positive integers $n>1$ and $k <n $, the number of ...
- 32.1k
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 ...
- 5,429
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). ...
- 48.9k
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$ ...
- 121
0
votes
1
answer
238
views
Graph alignment by considering node and edge weights
I have two complete weighted graphs, with the same number of nodes and edges. Each node has a multi-dimensional vector, which represents its features. Edge weights are float numbers between 0 to 1. I'...
- 101
1
vote
0
answers
183
views
Generalizing Hall's marriage theorem
(This question was earlier posted on stackexchange: Generalizing Hall's marriage theorem. As it received no answers there, I am reposting it here for more attention.)
Fix positive integers $m,n,k$ ...
- 410
3
votes
0
answers
231
views
Counting matchings and perfect matchings
A matching in a graph is a subset of the edges such that
no two edges share a vertex. A perfect matching is a matching where every vertex is part of exactly one edge in the matching.
Counting the ...
- 15.8k
30
votes
2
answers
3k
views
An unfair marriage lemma
I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem:
Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
- 13.4k
5
votes
1
answer
125
views
Generalization of Menger's theorem to infinite graphs
Aharoni and Berger generalized Menger's Theorem to infinite graphs: For any digraph, and any subsets $A$ and $B$, there is a family $F$ of disjoint paths from $A$ to $B$ and a set separating $B$ from $...
- 19.6k
6
votes
0
answers
296
views
Catalan numbers from matchings?
There are several examples of interpreting the Catalan numbers as non-nesting or non-crossing matchings of some graph.
My question is:
Is there a family of graphs $G_1,G_2,\dotsc$ with the number of ...
- 15.8k
15
votes
3
answers
613
views
Maximum matching in a graph with no "shortcuts"
For a directed acyclic graph (DAG) $G$, denote by $G^\star$ the undirected graph obtained from $G$ by ignoring direction of its arcs. Let $e(G)=e(G^\star)$ be the number of arcs in $G$ (or edges in $G^...
- 109k
6
votes
1
answer
538
views
Induced matching number
Definition:
A matching in a graph $G$ is a subgraph consisting of pairwise disjoint edges. If the subgraph is an induced subgraph, the matching is an induced matching. The largest size of an induced ...
- 32.1k
1
vote
0
answers
128
views
Hopcroft–Karp Algorithm for a dynamic graph
As so you all know, we have Hopcroft–Karp Algorithm for maximum matching between two sides in a bipartite graph. It runs in $O(\sqrt{V} \times E)$ where $V$ is the vertex set and $E$ is the edges set.
...
- 63.9k
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 ...
CommunityBot
- 1
0
votes
0
answers
110
views
Bound on the number of maximum matchings in a graph
It is known that the number of perfect matchings in a graph is bounded above by the integer part of the square root of the permanent of its adjacency matrix. But, suppose I take the square root of the ...
- 2,089
10
votes
0
answers
626
views
A rainbow perfect matching in an edge-colored graph with spanning color classes
This question is a sequel of my last question and is eventually motivated by recent advances in quantum physics. Given an even number $n\ge 6$ and a positive integer $k<n$, Claim from the linked ...
- 5,409
4
votes
1
answer
193
views
Is König's Property for graphs inheritable from finite subgraphs?
Let $G = (V,E)$ be a simple, undirected graph. A set $C \subseteq V$ is said to be a (vertex) cover if $C \cap e \neq \emptyset$ for all $e\in E$. A matching is a set $M\subseteq E$ of pairwise ...
- 12.9k
1
vote
0
answers
113
views
Do I need to find a maximum matching to get the matching number of a graph?
Let’s say we are talking about a simple undirected graph with no loops and no multiple edges. But not necessarily bipartite. And we need to find its matching number. Do we have to find a maximum ...
- 111
1
vote
2
answers
146
views
What's the name of the graph operation of connecting two copies of a graph with a perfect matching?
Let $G=(V_1,E_1)$ be a simple graph with vertex set $\{v_1,v_2,\ldots,v_n\}$ and let $G'=(V_2,E_2)$ be another copy of $G$ with vertex set $\{u_1,u_2,\ldots,u_n\}$. Assume $V_1\cap V_2= \emptyset$.
...
- 6,969
0
votes
1
answer
338
views
Stable marriages for infinite bipartite graphs
Short and informal version: Does the stable marriage problem have a solution if there are $\kappa$ men and $\kappa$ women for any cardinal $\kappa \geq \aleph_0$?
Long and formal version: Let $\kappa$...
- 32.1k
3
votes
1
answer
131
views
A graph $G$ with two $K_6$ subgraphs, in which any one-factor of $G$ induces a one-factor in exactly one of the $K_6$ subgraphs?
I'm seeking a simple graph $G$ of the following type:
It contains two disjoint copies of $K_6$ (the complete graph on 6 nodes), $H$ and $H'$ say.
Any one-factor of $G$ must contain either (a) a one ...
- 32.1k
6
votes
1
answer
230
views
A non-distinct system of representative edges
I have the following problem:
Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs on the same vertex set. I would like to find a "system of representative edges" $ f : \mathcal{G} \...
- 1,701
7
votes
2
answers
480
views
Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?
Let $f(G)$ give the number of perfect matchings of a graph $G$.
Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Consider collection of all $2n$ vertex balanced bipartite graph to be $\...
- 32.1k
11
votes
5
answers
2k
views
Are all almost regular graphs obvious?
Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively.
A graph is almost regular if $\Delta-\delta=1$.
Now, here is a simple way to generate ...
- 32.1k
0
votes
0
answers
71
views
A counterexample of a theorem about matching extendable
$M$ is perfect if $M$ covers all vertices of $G$, and $M$ is extendable if $G$ has a perfect matching containing $M$. Moreover, a graph $G$ with at least $2k + 2$ vertices is said to be $k$-extendable ...
- 1,851
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$?
- 32.1k
7
votes
2
answers
500
views
Disjoint perfect matchings in complete bipartite graph
Let $K_{n,n}$ be a complete bipartite graph with two parts $\{u_1,u_2,\ldots,u_n\}$ and $\{v_1,v_2,\ldots,v_n\}$, and let $K^-_{n,n}$ be the graph derived from $K_{n,n}$ by delete a perfect matching $\...
- 341
3
votes
2
answers
388
views
Maximum matchings in infinite graphs
For any graph $G=(V,E)$ we define $\mu(G) = \sup\{|M|: M\subseteq E(G) \text{ is a matching}\}$.
Is there a graph $G=(V,E)$ such that for every matching $M\subseteq E$ we have $|M|<\mu(G)$?
- 32.1k
3
votes
1
answer
376
views
Generalization of Marshall Hall's Theorem to non-simple bipartite graphs
Lemma 8.6.5 of the book "Matching Theory" by Lovász and Plummer states the following lemma:
Lemma: Let $G$ be a simple bipartite graph with bipartition $(A,B)$, and assume that each point ...
- 32.1k
8
votes
1
answer
384
views
Berge-Fulkerson conjecture --- the planar case
A well-known conjecture of Berge and Fulkerson says that every bridgeless cubic graph has a collection of six perfect matchings that together cover every edge exactly twice. Is this still open for ...
- 32.1k
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 ...
- 1,769
13
votes
1
answer
3k
views
Is there a version of König's theorem for tripartite 3-graphs?
I would like to know if there exists a version of König's theorem for tripartite $3$-graphs.
In other words, let $G = (V,T)$ be a tripartite $3$-graph. That is, $V$ is a set of vertices (with $V$ ...
- 32.1k
1
vote
0
answers
80
views
Is there any theorem similar to the Tutte–Berge formula?
Tutte–Berge formula is a characterization of the size of a maximum matching in a graph.
The theorem states that the size of a maximum matching of a graph
${\displaystyle G=(V,E)}$ equals $${\...
- 1,851
8
votes
2
answers
760
views
Maximum number of perfect matchings in a planar graph?
What is the maximum number of perfect matchings a planar $k$-partite $|V|$ number of vertices simple graph can have where $k=2,3,4$ ($k>4$ is impossible for a planar graph)?
Since number of ...
- 761
2
votes
0
answers
44
views
Which edges to delete from cubic graphs to get good cycle covers?
Let $G\left(V,E\subset V\times V,\omega: V\supset \lbrace u,v\rbrace\mapsto w_{uv}\in\mathbb{R}\right);\ \left|e_{uv}\right|:=\omega_{uv}\quad$ be a cubic symmetric graph that contains a vertex-...
- 3,065
3
votes
1
answer
80
views
Determining a specific perfect matching $M$ by repeatedly asking for $|M \cap M_i|$ for other perfect matchings $M_i$
Let $G=(V,E)$ be a complete bipartite graph with $2n$ vertices and $M \subset E$ some unknown perfect matching of $G$.
The goal is to determine $M$ by repeatedly choosing some perfect matching $M_i \...
- 314
3
votes
1
answer
177
views
Maximum weight matching with classes of edges in a multi-edge bipartite graph
Consider a multi-edge bipartite graph $G = (L, R, E)$, with $|L| = |R| = n$, such that any $x \in L, y \in R$ have precisely two edges in $E$, $(x, y)_r, (x,y)_b$. We can imagine that we are assigning ...
- 314
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'}$ ...
- 1,042
1
vote
0
answers
61
views
Algorithm for minimum weight matching with "tree topology"
Given a finite graph $G(V,E)$ with undirected and weighted edges, whose set of vertices $V$ is partitioned into a collection $\mathfrak{P}=\lbrace V_1,\,\dots,\,V_k\rbrace$ of non-empty and pairwise ...
- 3,065
0
votes
0
answers
26
views
Complexity of heaviest 2-optimal vertex-disjoint cycle covers
Calculating lightest vertex-disjoint cycle covers of finite complete symmetric graphs with weighted edges can be done efficiently and also renders the edge set of the calculated cycles free of pairs ...
- 13.2k
1
vote
0
answers
123
views
Number of maximum matchings in bipartite graphs of positive surplus
Let $G$ be a simple bipartite graph with left part $L(G)$ and right part $R(G)$. For $S \subseteq L(G)$, denote $N(S)$ the set of neighbours of vertices of $S$. Define the surplus $s(G)$ as $\min_{S \...
- 5,590
3
votes
1
answer
304
views
Perfect matchings in infinite regular bipartite graphs
This question was motivated by a discussion here and is related to a previous question here.
Let $\kappa$ and $\lambda$ be cardinals such that $0<\lambda\leq \kappa$. Let $G=(A\cup B, E)$ be a ...
- 1,701