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
2 votes
1 answer
126 views

Bipartite matching with a pairwise constraint

A long time ago I remember seeing a very clever construction for the following problem, but I can't find a reference for it anywhere: suppose I have a bipartite graph $G=(U\cup V, E)$, and the ...
Tom Solberg's user avatar
  • 3,910
4 votes
0 answers
116 views

Reorganizational matching

Motivation. My friend works in an organization that is re-organizing itself in the following somewhat laborious way: There are $n$ people currently sitting on $n$ jobs in total (everyone has one job). ...
Dominic van der Zypen's user avatar
2 votes
0 answers
132 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
0 votes
1 answer
26 views

Calculating vertex potentials from optimal matchings

Question: can the solution to the dual of a Linear Program be calculated directly from the solution of the primal Linear Program? If yes, what are known algorithms and their bounds on complexity. As ...
Manfred Weis's user avatar
  • 12.6k
0 votes
0 answers
23 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.6k
0 votes
1 answer
159 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
109 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
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.6k
1 vote
0 answers
137 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
94 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
127 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
158 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
70 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.6k
6 votes
0 answers
242 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.6k
1 vote
0 answers
25 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
22 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
109 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
73 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
65 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.6k
0 votes
1 answer
93 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.6k
0 votes
0 answers
102 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,007
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
134 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.6k
4 votes
1 answer
188 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
55 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
90 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.6k
1 vote
0 answers
109 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
141 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
67 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,605
7 votes
2 answers
403 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,130
3 votes
1 answer
326 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
367 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,130
5 votes
1 answer
681 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
44 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.6k
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,092
1 vote
0 answers
77 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,605
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.6k
1 vote
1 answer
46 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.6k
3 votes
1 answer
76 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
139 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
269 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.6k
1 vote
0 answers
58 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.6k
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.6k
3 votes
1 answer
257 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
75 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
118 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
262 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,666
4 votes
2 answers
242 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,666