# 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
Filter by
Sorted by
Tagged with
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' ...
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'...
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 ". ...
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
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$ ...
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
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$...
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
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$-...
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 ...
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 ...
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
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 ...
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
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
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 ...
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, ...
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 ...
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
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
132 views

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
22 views

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 ...
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 ...
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 ...
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 ...
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
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 $G=(V,E)$ equals {\...
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
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 ...
64 views

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