Questions tagged [perfect-matchings]
A perfect matching is a matching of all the vertices of a graph. In other words, a perfect matching is a set of edges such that each vertex of the graph is incident to exactly one edge in the set.
142 questions
1
vote
1
answer
193
views
Curious identity involving the number of perfect matchings of the complete graph
Can you prove (preferably combinatorially) the following identity for the total number of perfect matchings of the complete graph $K_{2n}$, where the edges in the matching are ordered, i.e., $\binom{...
- 109
1
vote
1
answer
313
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'}$ ...
- 13.9k
1
vote
1
answer
95
views
Maximum number of perfect matchings in a graph of genus $g$ balanced $k$-partite graph
What is the maximum number of perfect matchings a genus $g$ balanced $k$-partite graph (number of vertices for each color in all possible $k$-colorings is within a difference of $1$) can have? I am ...
- 13.9k
1
vote
0
answers
17
views
Complexity of optimal cartesian matching
Question:
what is known about the algorithmic aspects of optimally matching a set $\mathcal{P} = \prod\limits_{i=1}^n \left(1,\,\cdots,\,k_i\right)$ of grid-points to a set of $\prod\limits_{i=1}^...
- 13.2k
1
vote
0
answers
34
views
Any updates on "The minimum cost perfect matching problem with conflict pair constraints"?
The subject of the paywalled article The minimum cost perfect matching problem with conflict pair constraints (MCPMPC) are perfect matchings of minimum cost that do not contain certain pairs of edges; ...
- 13.2k
1
vote
0
answers
129
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.
...
1
vote
0
answers
69
views
On perfect matchings on planar graphs - is there a linear time deterministic algorithm?
The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree.
MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time ...
- 13.9k
1
vote
0
answers
94
views
Number of extremal $\{0,1\}$ matrices having permanent $1$ property
Is there a function which describes the number of $\{0,1\}^{n\times n}\cap\mathbb Z^{n\times n}$ matrices having permanent $1$?
I think it might be $\mathsf{poly}(n!)$ bounded.
Is there a function ...
- 13.9k
1
vote
0
answers
53
views
Density of perfect matching count in $k$-partite graphs?
Let $f(G)$ give number of perfect matchings of a graph $G$.
Denote $\mathcal N_{n}=\{0,1,2,\dots,n!-1,n!\}$.
Denote collection of all $kn$ vertex balanced $k$-partite graph (each color is on $n$ ...
- 13.9k
1
vote
0
answers
112
views
Is there a bipartite graph whose determinant corresponds to number of perfect matchings?
Let $M\in\{0,1\}^{n\times n}$ be a square integer matrix. If we consider $M$ as biadjacency of a balanced bipartite graph on $2n$ vertices having $n$ vertices of color $1$ and $n$ vertices of color $2$...
- 13.9k
1
vote
0
answers
63
views
$1$-factorizability for linear hypergraphs with infinite edges on $\omega$
Let $H=(V,E)$ be a hypergraph. We say that $M\subseteq E$ is a matching if the members of $M$ are pairwise disjoint, and $M$ is said to be perfect if $\bigcup M = E$. Moreover, $H$ is $1$-factorizable ...
- 48.9k
1
vote
0
answers
147
views
A simple case of a strong version of the Berge-Fulkerson conjecture
UPDATE 28 June 2019 A counterexample for Conjecture 2 has been provided. The conjecture is now demoted again to guess. The text has been updated to reflect this change, and there is now a new ...
- 1,018
1
vote
0
answers
69
views
Perfect matchings and edge cuts in cubic graphs - part 1
Let $G$ be a bridgeless cubic (simple) graph, and let $M$ be a perfect matching in $G$. $G-M$ will necessarily be a set of circuits. For example, if we delete a perfect matching from $K_{3,3}$ we ...
- 1,018
1
vote
0
answers
27
views
Complexity of Calculating Minimum Weight Final Perfect Matchings
It is known, that Minimum Weight Perfect Matching can be calculated in $O(n^3)$;
Furthermore, it is possible, that the edge sets of the Minimum Weight Perfect Matching and of the Maximum Weight ...
- 13.2k
1
vote
0
answers
299
views
On Schrijver's lower bound for the number of perfect matchings
Schrijver's lower bound gives the number of perfect matchings in a $k$-regular bipartite graph as $\Big(\frac{(k-1)^{k-1}}{k^{k-2}}\Big)^n$. What is the corresponding lower bound for minimum-degree $k$...
- 13.9k
1
vote
0
answers
166
views
Expected number of perfect matchings in bounded degree bipartite graphs
Consider collection $\mathcal C_{n,n,\Delta}$ of every $2n$ vertex balanced bipartite graph of average degree $\Delta$.
What is the expected number of perfect matching a graph in $\mathcal C_{n,n,\...
- 13.9k
1
vote
0
answers
66
views
Largest number of perfect matchings in bounded genus graphs
What is the largest number of perfect matchings a genus $g$ bipartite graph on $n+m$ vertices have?
- 13.9k
0
votes
3
answers
106
views
Calculating variance-minimal perfect matchings
Question:
are there any algorithms, resp. what can be recommended, for calculating perfect matchings with the property that the variance of their edge's weights is minimal?
- 13.2k
0
votes
1
answer
163
views
Minimum-weight disjoint union of perfect matchings
Is there a counter example or proof for the claim that the lightest edge-disjoint union of a pair of perfect matchings contains the edges of the lightest perfect matching in a finite complete graph ...
- 13.2k
0
votes
1
answer
38
views
Edge-length constraints from greedy matching
The subject of this question are perfect matchings of a complete undirected graph $G(V,E), n:=\mathrm{card}(V)=2k$, without self-loops or parallel edges and $n=2k$ vertices.
The objective is to ...
- 13.2k
0
votes
1
answer
112
views
Weak $1$-factorizability
A simple, undirected graph is said to be $1$-factorizable if there is a partition of the edge set $E$ such that every member of the partition is a perfect matching of $G$. Let us call $G$ weakly $1$-...
- 48.9k
0
votes
1
answer
358
views
A vertex transitive graph has a near perfect/ matching missing an independent set of vertices
Consider a power of cycle graph $C_n^k\,\,,\frac{n}{2}>k\ge2$, represented as a Cayley graph with generating set $\{1,2,\ldots, k,n-k,\ldots,n-1\}$ on the Group $\mathbb{Z}_n$. Supposing I remove ...
- 2,089
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)....
- 6,962
0
votes
0
answers
43
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
0
votes
0
answers
13
views
Enumerating the directed vertex-disjoint cycle covers of digraphs
A directed cycle-cover of a digraph $D$ is in the sense of this post equivalent to a perfect matching in the related undirected biadjacency graph $B$ in which the edges connect a vertex $u$ of $D$ in ...
- 13.2k
0
votes
0
answers
11
views
Detecting non-optimality in disjoint unions of perfect matchings
This is a follow-up question to Minimum-weight disjoint union of perfect matchings:
let $G$ be a complete symmetric graph with $2n$ vertices, whose edges are mapped to their weights by $\omega()$ and ...
- 13.2k
0
votes
0
answers
28
views
Calculation of cardinality constrained minimum weight matchings
Given a complete weighted graph $G(V,E),\ |V|=2n$, calculating a minimum weight matching with $n-k$ edges can be reduced to calculating a perfect matching in $H(V+U,E+F),\ |U|=2k,\ F=(u\in U,v\in V),\ ...
- 13.2k
0
votes
1
answer
171
views
How to understand Chegireddy-Hamacher's algorithm for finding k-best perfect matching
I am reading Algorithms for finding K-best perfect matchings by Chegireddy and Hamacher, and I have trouble to understand their Section 2 "General algorithm for K-best perfect matchings ". ...
- 163
0
votes
0
answers
35
views
Finding a bipartite graph that contains a specific elements of perfect matchings
I am a physicist who is interested in the applications of graph theory.
I've been studying the bipartite graphs and perfect matching finding problems. I see there are several research works on ...
0
votes
0
answers
84
views
Bounds for smallest non-trivial designs
Given $s>t\ge 2$, let $N(s,t)$ be the smallest integer $n>s$ such that there exists an “$(n;s;t;1)$-design” (i.e., a collection of $s$-subsets $e_1,\dots,e_m$ of $[n]:=\{1,\dots,n\}$, such that ...
- 3,499
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
0
votes
0
answers
48
views
Spanning subgraphs defined via $K_4$ matchings
I have by accident found an interesting kind of spanner of complete symmetric graphs $G(V,E)$ with weighted edges.
What I actually had planned was to implement an algorithm for calculating certain non-...
- 13.2k
0
votes
1
answer
150
views
Combining three matchings to form a maximal matching
Consider a regular tripartite graph $G$ with maximum degree $\Delta\ge3$ and parts $A,B,C$. Now, the induced subgraphs $A\cup B, B\cup C$ and $A\cup C$ are all bipartite.
Now, is there a way to ...
- 2,089
0
votes
0
answers
54
views
Do all induced subgraphs of powers of cycles have a perfect matching
Do all independence induced subgraphs of powers of cycles have a distinct 1-factor? By independence induced, I mean those induced subgraphs which are formed by removing a maximal independent set of ...
- 2,089
-1
votes
2
answers
306
views
Cardinality of a set of mutually disjoint perfect matchings of $K_\omega$
If $G=(V,E)$ is a simple, undirected graph, we say that $M\subseteq E$ is a perfect matching if the members of $M$ are pairwise disjoint and $\bigcup M = V$. Let $K_\omega$ be the complete graph on $\...
- 48.9k
-2
votes
1
answer
362
views
Infinite graphs with large degree but no perfect matching [duplicate]
Is there an example of an infinite connected, simple, undirected graph $G = (V,E)$ such that every vertex has $|V|$ neighbors, but $G$ does not have a perfect matching (that is, a set $M\subseteq E$ ...
- 48.9k
-2
votes
2
answers
2k
views
Does every 3-regular bridgeless graph have a perfect matching? [closed]
Let $G$ be a simple $3$-regular (every vertex has degree $3$) $2$-edge connected graph. Does $G$ contain a perfect matching?
- 17
-2
votes
1
answer
640
views
About structure of the set of perfect matchings of $K_{n,n}$
Are there any special properties known about the set of perfect matchings of $K_{n,n}$? Like any global structure of this set? Some natural way to partition it? Like is there some algebraic structure ...
- 1,893
-2
votes
1
answer
74
views
Matching and minimal degree
Let $n\in\mathbb{N}$ be a positive integer and let $G =(V,E)$ be a connected simple undirected graph with $|V| = 2n$. Is it true that if for the minimal degree $\delta(G)$ we have $\delta(G) \geq n$, ...
- 48.9k
-2
votes
1
answer
174
views
What is known about iterated matching as a TSP heuristic
A fairly wellknown heuristic for TSP that is based on matching is described in the 2003 paper Match twice and stitch: a new TSP tour construction heuristic by Andrew B. Kahng and Sherief Reda.
Its ...
- 13.2k
-3
votes
1
answer
125
views
Does the Hadwiger-Nelson graph have a perfect matching?
The Hadwiger-Nelson graph on $\mathbb{R}^n$ is defined to be $(\mathbb{R}^n,E_n)$ where $$E_n = \big\{\{x,y\}: x,y\in \mathbb{R}^n \text{ and } |x-y|=1\big\},$$ where $|\cdot|$ denotes the Euclidean ...
- 48.9k
-4
votes
1
answer
158
views
Connected infinite graph $G$ with $\delta(G)\geq 2$ and no perfect matching [closed]
Is there a connected infinite graph $G=(V,E)$ such that $\text{deg}(v) \geq 2$ for all $v\in V$, and $G$ possesses no perfect matching?
- 48.9k