Skip to main content

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.

Filter by
Sorted by
Tagged with
2 votes
0 answers
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 ...
Agile_Eagle's user avatar
4 votes
1 answer
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, ...
Agile_Eagle's user avatar
0 votes
0 answers
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 ...
Manfred Weis's user avatar
  • 12.7k
2 votes
0 answers
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$ ...
errorist's user avatar
  • 121
2 votes
0 answers
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 ...
Manfred Weis's user avatar
  • 12.7k
0 votes
0 answers
23 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),\ ...
Manfred Weis's user avatar
  • 12.7k
6 votes
1 answer
243 views

Pair matching between divisors less and more than $\sqrt{N}$

Let $n$ be the positive integer. Let $A$ and $B$ be sets of divisors of $n$ less and more than $\sqrt{n}$ respectively. Consider bipartite graph $(A, B)$, where two vertices are connected when one ...
thematdev's user avatar
  • 163
0 votes
1 answer
123 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 ". ...
fagd's user avatar
  • 163
4 votes
1 answer
105 views

Are there decompositions of $K_{16}$ by certain 3-regular graphs?

This is inspired by the problem of the Hoffman-Singleton Decomposition of $K_{50}$. I wanted to look at smaller variants of this kind of problem, and so naturally I started wondering: Can the (edges ...
Wolfgang's user avatar
  • 13.2k
0 votes
0 answers
12 views

Reducing minimum-weight $f$-subfactors to minimum-weight perfect matching

Question: What is known about reducing the calculation of minimum-weight $f$-subfactors of symmetric graphs in the presence of negative edge weights to minimum-weight perfect matching? By a $f$-...
Manfred Weis's user avatar
  • 12.7k
0 votes
0 answers
98 views

Finding minimum weight perfect matchings for the same graph with slightly different edge weights

Suppose I have found the minimum weight perfect matching (MWPM) for a given weighted graph, with say, the Blossom algorithm. Now if the weights of a small subset of edges are changed in the graph, how ...
fagd's user avatar
  • 163
2 votes
0 answers
93 views

Counting number of perfect matchings

Counting perfect matchings in bipartite graphs is $\# P$ complete. Let $G(V,E)$ be a graph known to have $d$ number of perfect matchings. Bipartite it the obvious way by adding $E$ vertices with one ...
Turbo's user avatar
  • 13.7k
2 votes
2 answers
119 views

Existence of certain regular graphs

Question: what can be said about the existence of $2k$ regular graphs, $1\lt k$ that have a $1$-factor and a $2$-factor? Provided their existence, what is/are the smallest for $k$? The graphs must be ...
Manfred Weis's user avatar
  • 12.7k
3 votes
0 answers
166 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 ...
Per Alexandersson's user avatar
0 votes
0 answers
32 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 ...
Beom.Jean's user avatar
3 votes
2 answers
388 views

An "incomplete" tiling?

Given an $m\times n$ chess board, we place $p$ $2\times 1$ dominoes on the board so that they don't overlap. How many ways can we place them? When each square of the board is covered by a domino this ...
Jiyuan Zhang's user avatar
0 votes
0 answers
81 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 ...
Zach Hunter's user avatar
  • 3,413
0 votes
1 answer
35 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 ...
Manfred Weis's user avatar
  • 12.7k
1 vote
0 answers
111 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. ...
linuxbeginner's user avatar
1 vote
1 answer
185 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{...
sdd's user avatar
  • 109
0 votes
0 answers
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 ...
vidyarthi's user avatar
  • 2,079
1 vote
1 answer
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, ...
Manfred Weis's user avatar
  • 12.7k
4 votes
2 answers
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 ...
Sanchayan Dutta's user avatar
7 votes
0 answers
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 ...
Michał Oszmaniec's user avatar
1 vote
0 answers
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 ...
Turbo's user avatar
  • 13.7k
1 vote
2 answers
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$. ...
W. Paul Liu's user avatar
3 votes
1 answer
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 ...
L.C. Zhang's user avatar
  • 1,645
2 votes
0 answers
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 ...
Turbo's user avatar
  • 13.7k
7 votes
2 answers
418 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 $\...
Xin Zhang's user avatar
  • 1,140
3 votes
1 answer
337 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 ...
Sanket Biswas's user avatar
7 votes
1 answer
370 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 ...
Xin Zhang's user avatar
  • 1,140
8 votes
0 answers
242 views

Sum of perfect matching construction

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 ...
Turbo's user avatar
  • 13.7k
1 vote
1 answer
110 views

Succinct polynomial sized representation of balanced bipartite graphs whose perfect matching count is a primorial

Is there a $P$ time definable sequence of succinct polynomial sized representation of balanced bipartite graphs whose number of perfect matchings is a primorial? For factorial a complete bipartite ...
Turbo's user avatar
  • 13.7k
5 votes
1 answer
829 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
10 votes
0 answers
607 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 ...
Alex Ravsky's user avatar
  • 4,112
2 votes
1 answer
384 views

At most one perfect matching of a bipartite graph

I. Given biadjacency matrix $A$ of a bipartite graph on $2n$ vertices having $n$ vertices of either color on the constraints the graph either has $0$ perfect matchings $1$ perfect matchings is it ...
User2021's user avatar
2 votes
0 answers
69 views

Why is Schröder numbers equivalent to the number of perfect matchings for triangular grid of n squares and how the graph look like? [duplicate]

In the OEIS entry for the Schröder numbers is A006318. There is a comment which related the sequence to perfect matchings: The number of perfect matchings in a triangular grid of n squares (n = 1, 4, ...
Xuemei's user avatar
  • 141
4 votes
0 answers
187 views

Dyadic distribution of $0/1$ permanents

Fix reals $a,b\in(1,2)$ satisfying $1<b<a<ab<2$. What fraction of $0/1$ matrices of dimensions $n\times n$ have permanents in $[b2^m,a2^m]$ at some $m\in\{0,1,2,\dots,\lfloor\log_2n!\...
Turbo's user avatar
  • 13.7k
2 votes
0 answers
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 ...
NeoN's user avatar
  • 241
0 votes
1 answer
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 ...
Manfred Weis's user avatar
  • 12.7k
5 votes
2 answers
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 ...
PickupSticks's user avatar
1 vote
0 answers
92 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 ...
Turbo's user avatar
  • 13.7k
3 votes
1 answer
78 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 \...
Dario's user avatar
  • 149
1 vote
1 answer
290 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.7k
0 votes
0 answers
38 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-...
Manfred Weis's user avatar
  • 12.7k
1 vote
0 answers
50 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$ ...
Turbo's user avatar
  • 13.7k
1 vote
0 answers
109 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$...
Turbo's user avatar
  • 13.7k
2 votes
1 answer
121 views

Mod $2$ information on perfect matchings in general graphs

Determinant modulo $2$ of biadjacency matrix of bipartite graphs provide mod $2$ information on number of perfect matchings on bipartite graphs providing polynomial complexity in bipartite situations. ...
Turbo's user avatar
  • 13.7k
3 votes
1 answer
275 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 ...
Louis D's user avatar
  • 1,676
3 votes
0 answers
88 views

Infection on a complete graph

Suppose we have a complete graph on $2n$ vertices with one "infected" vertex. At each time step, we form a matching of the vertices. Then the vertices paired with infected vertices will also ...
PoissonSummation's user avatar