# 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.

136 questions
Filter by
Sorted by
Tagged with
67 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 ...
• 167
154 views

### Algorithms to count perfect matchings in near planar graphs

It is well known that counting perfect matchings is tractable in planar graphs (due to Kastelyn). I am interested in classes of (for lack of a better word) "near" planar graphs (1-planar, ...
• 167
10 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 ...
• 12.7k
139 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
72 views

### Optimal perfect matchings in magic squares

Question: what is known about minimum/maximum weight perfect matchings in magic squares with or without special properties like e.g. being pandiagonal? I am especially interested minimal/maximal ...
• 12.7k
23 views

• 109
103 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,079
1 vote
81 views

### Symmetry of optimal solutions to symmetric assignment problems

Is there a sound proof of or a counter example to the following conjecture: if $\boldsymbol{A}^T=\boldsymbol{A}$ is the cost-matrix of a bipartite assignment problem with unique optimal assignment, ...
• 12.7k
281 views

### Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment

I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
200 views

### Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs

Let $G=(V,E)$ be a graph with an even number of vertices $|V|=2n$. Assume that $G$ is $K_{3,3}$-free i.e. it does not contain a graph isomorphic to biclique $K_{3,3}$. A perfect matching of $G$ is a ...
1 vote
66 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.7k
1 vote
144 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$. ...
• 557
521 views

### The perfect matching problem of planar graph

We know that connectivity is closely related to the Hamiltonian of planar graphs. The most famous result is the Tutte theorem. Theorem (Tutte, 1956). A 4-connected planar graph has a Hamiltonian ...
• 1,645
60 views

### Sum of number of perfect matchings and a constant constuction

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...
• 13.7k
418 views

• 13.7k
90 views

### Computing bipartite matching of size $k$?

Given a bipartite graph with $n$ vertices on each side and an integer $k$, how can we compute all bipartite matchings of size $k$? The problem of computing all perfect matchings is #P-complete. But I ...
• 241
149 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 ...
• 12.7k
524 views

### Smallest $3$-regular graph with a unique perfect matching

What is the smallest 3-regular graph to have a unique perfect matching? With a large enough number of nodes, it is possible for a 3-regular graph to have no perfect matching (example can be seen in ...
• 169
1 vote
### 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 ...