# Questions tagged [matching-theory]

For questions about matchings in graph theory. A matching on a graph is a set of edges such that no two edges share a common vertex.

164
questions

0
votes

0
answers

18
views

### Calculating minimum weight matchings in graphs with self-loops

Question:
which of the minimum-weight perfect matching algorithms can properly deal with the presence of self-loops?
The motivation for the question is the calculation of minimum-weight 'imperfect' ...

0
votes

1
answer

59
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'...

0
votes

1
answer

61
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 ". ...

0
votes

0
answers

10
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$-...

1
vote

0
answers

118
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$ ...

0
votes

0
answers

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

1
vote

0
answers

118
views

### Random graphs constructed by many large matchings

Let $G_{n,d}$ be $d$-regular random graph. We know that for $d \geq 3$, $G \in G_{n,d}$ a.a.s. has a $1$-factorisation when $n$ is even.
So, the resulting graph that obtained from randomly choosing $d$...

3
votes

0
answers

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

1
vote

1
answer

55
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$-...

6
votes

0
answers

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

0
votes

0
answers

22
views

### Applicability of matching to tour improvement

Question:
what are relevant publications that deal with matching as a means of constructing shorter tours from existing ones?
The reason for asking is that I couldn't find anything in that respect ...

0
votes

0
answers

27
views

### Complexity of a specific constrained maximum weight matching

Let $G(V,E)=K_n$ be a complete symmetric and edge-weighted graph with $n$ vertices and let $H$ be a Hamilton cycle in $G$, i.e. a connected $2$-factor.
Question:
what is the complexity of calculating ...

1
vote

0
answers

19
views

### Path cover with sets of nodes

I am considering the following variant of the path-cover problem. I have an acyclic directed graph G=(V,E). Moreover, the set V is partitioned into $V=V_1 \cup ... \cup V_k$ (these sets are pairwise ...

0
votes

1
answer

21
views

### Pairing optimisation w.r.t. a given function, or at least close to optimised

Suppose you have a set of objects X and a scoring function f (in which order does not matter; f(x,y) = f(y,x)) which works in the following way.
Passing a viable pair of these objects to the function ...

1
vote

0
answers

90
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

62
views

### Concavity of expected size of a maximum matching (in a bipartite graph) w.r.t. edge probability

Given a n*n bipartite graph where each edge (between any two nodes on the opposite side) is formed i.i.d. with probability $p$, can we show a concavity result on the expected size of a maximum ...

0
votes

0
answers

60
views

### Validity of an argument for an implication of NP-Completeness

Fedor Petrov has posed a notorious problem regarding the existence of a matching in this question: Resolution of multiple edges
As I see it the setting is a constrained bipartite matching and thus, ...

0
votes

1
answer

69
views

### $\mathrm{ILP}$-formulation for Minimum Maximal Matching (MMM) Problem

Despite some online searching I couldn't find examples of dedicated Integer Linear Programs ($\mathrm{ILP}$s) for determining smallest matchings, that are not contained in a larger one.
It seems that ...

0
votes

0
answers

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

1
vote

1
answer

89
views

### Hypergraphs with finite matching / covering balance

Let $H=(V,E)$ be a hypergraph such that $\emptyset\notin E$. We say that $C\subseteq V$ is a (vertex) cover if for all $e \in E$ we have $C\cap e\neq \emptyset$. The minimum size that a cover can have ...

1
vote

1
answer

132
views

### Interpreting optimal matchings as permutations

If $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ is the cost-matrix of an assignment problem, then the usual statement of the problem of finding an optimal assignment is to identify $n$ elements $a_{i,\,\...

4
votes

1
answer

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

1
vote

1
answer

53
views

### Maximal matchable set in hypergraph with finite edges

Let $H=(V,E)$ be a hypergraph. A set $M\subseteq E$ consisting of mutually disjoint members of $E$ is said to be a matching. We say $S\subseteq V$ is matchable if there is a matching $M$ such that $\...

2
votes

2
answers

86
views

### Matching number in infinite hypergraphs

If $H= (V,E)$ is a hypergraph, a matching is a set $M\subseteq E$ such that $e_1\cap e_2 = \emptyset$ whenever $e_1\neq e_2 \in M$. The matching number $\mu(H)$ of a hypergraph $H=(V,E)$ with $V$ ...

1
vote

0
answers

22
views

### Topology of densest graphs whose optimal $3D$-matching can be calculated efficiently

let $A=\lbrace a_1,\,\dots,\,a_k\rbrace $ and $B=\lbrace b_1,\,\dots,\,b_{2k}\rbrace,\ A\cap B=\emptyset$ be be a partition of a graph's vertex set $V$, i.e. $V\,=\,A\cup B$.
Question:
has $G:=\...

1
vote

0
answers

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

1
vote

2
answers

134
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$.
...

0
votes

0
answers

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

7
votes

2
answers

325
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 $\...

3
votes

1
answer

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

7
votes

1
answer

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

5
votes

1
answer

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

0
votes

1
answer

43
views

### Name for a type of assignment task

given a bipartite graph $G(U,V,E\subseteq U\times V)$ with strictly positive edge-weights; is there an established name for the the task of calculating the lightest spanning subgraph and what is the ...

9
votes

0
answers

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

1
vote

0
answers

75
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 $${\...

2
votes

0
answers

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

1
vote

1
answer

43
views

### Finding optimal cycle covers with fixed number of vertices

Optimal vertex-disjoint cycle covers of weighted symmetric graphs with $n$ vertices can be calculated efficiently with the method of Tutte.
It is also possible to efficiently calculate optimal ...

3
votes

1
answer

64
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 \...

3
votes

1
answer

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

1
vote

1
answer

234
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
vote

0
answers

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

0
votes

0
answers

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

3
votes

1
answer

218
views

### Assignment problem with priorities and scores

I have run into a real problem that is actually a sort of assignment problem. I am describing it here because I am interested in knowing whether this problem already has a name (and whether there is ...

2
votes

0
answers

73
views

### Counting matchings in middle levels of the Boolean lattice

Let $k$ be a nonnegative integer and consider $C_k$, the set of all subsets $A$ of size $k$ in $[2k+1]=\{1,2,\ldots,2k+1\}$ as well as $C_{k+1}$, the set of all subsets $B$ of size $k+1$ in $[2k+1]$. ...

1
vote

0
answers

108
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 \...

3
votes

1
answer

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

4
votes

2
answers

236
views

### Relationship between minimum vertex cover and matching width

Let $H$ be a 3-partite 3-uniform hypergraph with minimum vertex cover number $\tau(H)$ (i.e. $\tau(H)=\min\{|Q|: Q\subseteq V(H), e\cap Q\neq \emptyset \text{ for all } e\in E(H)\}$).
Question: Is $\...

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

3
votes

1
answer

52
views

### $1$-factorizability for "complete" finite hypergraphs

Let $H=(V,E)$ be a hypergraph such that $V\neq \varnothing$ and $\varnothing \notin E$. A matching is a subset $M\subseteq E$ such that $m_1\neq m_2 \in M$ implies $m_1\cap m_2 = \varnothing$, and $M$ ...

0
votes

0
answers

61
views

### Birkhoff's theorem for hypergraphs

Birkhoff's theorem says that, in a bipartite graph $G$ in which both sides have size $n$, any fractional matching of size $n$ can be presented as a convex combination of integral matchings of size $n$ ...