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.

Filter by
Sorted by
Tagged with
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' ...
Manfred Weis's user avatar
  • 12.3k
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'...
Danial's user avatar
  • 101
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 ". ...
fagd's user avatar
  • 163
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$-...
Manfred Weis's user avatar
  • 12.3k
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$ ...
MathManiac's user avatar
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 ...
fagd's user avatar
  • 163
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$...
Zhukui Bai's user avatar
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 ...
Per Alexandersson's user avatar
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$-...
Manfred Weis's user avatar
  • 12.3k
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 ...
Per Alexandersson's user avatar
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 ...
Manfred Weis's user avatar
  • 12.3k
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 ...
Manfred Weis's user avatar
  • 12.3k
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 ...
Andres Fielbaum's user avatar
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 ...
Seb's user avatar
  • 3
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. ...
linuxbeginner's user avatar
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 ...
messi22's user avatar
  • 53
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, ...
Manfred Weis's user avatar
  • 12.3k
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 ...
Manfred Weis's user avatar
  • 12.3k
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 ...
vidyarthi's user avatar
  • 1,833
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 ...
Dominic van der Zypen's user avatar
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,\,\...
Manfred Weis's user avatar
  • 12.3k
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 ...
Dominic van der Zypen's user avatar
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 $\...
Dominic van der Zypen's user avatar
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$ ...
Dominic van der Zypen's user avatar
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:=\...
Manfred Weis's user avatar
  • 12.3k
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 ...
Iterokun 's user avatar
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$. ...
W. Paul Liu's user avatar
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 ...
L.C. Zhang's user avatar
  • 1,353
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 $\...
Xin Zhang's user avatar
  • 1,040
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 ...
Sanket Biswas's user avatar
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 ...
Xin Zhang's user avatar
  • 1,040
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 ...
Sanket Biswas's user avatar
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 ...
Manfred Weis's user avatar
  • 12.3k
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 ...
Alex Ravsky's user avatar
  • 3,062
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 $${\...
L.C. Zhang's user avatar
  • 1,353
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-...
Manfred Weis's user avatar
  • 12.3k
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 ...
Manfred Weis's user avatar
  • 12.3k
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 \...
Dario's user avatar
  • 149
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 ...
arealguru's user avatar
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'}$ ...
Turbo's user avatar
  • 13.5k
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 ...
Manfred Weis's user avatar
  • 12.3k
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 ...
Manfred Weis's user avatar
  • 12.3k
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 ...
Vicent's user avatar
  • 143
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]$. ...
Abdelmalek Abdesselam's user avatar
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 \...
Mikhail Tikhomirov's user avatar
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 ...
Louis D's user avatar
  • 1,626
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 $\...
Louis D's user avatar
  • 1,626
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 ...
Dominic van der Zypen's user avatar
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$ ...
Dominic van der Zypen's user avatar
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$ ...
Erel Segal-Halevi's user avatar