All Questions
Tagged with matching-theory graph-theory
128 questions
0
votes
0
answers
42
views
How to determine if two matchings are related by a permutation?
Let $n \geq 2$ be an integer. Let
\begin{align*}
V &= \{(i, j); 1 \leq i, j \leq n \text{ and } i \neq j \} \\
E &= \{ \{v_1, v_2\}; v_1, v_2 \in V \text{ and } v_1 \neq v_2 \}.
\end{align*}
...
- 5,215
0
votes
1
answer
77
views
Bipartite matching where every adjacent pair of vertex on the left side of the graph has at least 1 vertex matched
The question is as stated above. I want to devise bipartite matching algorithm where it determies whether every adjacent pair of vertex on the left side of the bipartite graph has at least 1 vertex ...
1
vote
0
answers
48
views
How to solve a optimal matching problem where the "quality" of matching is only determined once all nodes are matched
Note: I'm not a mathematician; I'm just a biologist with basic math background trying to solve a scientific problem, so please excuse my ignorance.
The gist of the problem is as follows:
I have two ...
3
votes
1
answer
140
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 ...
- 129
1
vote
1
answer
54
views
Complexity of maximum weight-sum matching for cycle graphs
I need to determine a matching with maximal weight-sum for a cycle graph with positive, negative and zero edge-weights.
Question:
What is the fastest way of calculating such a matching?
Because of ...
- 13.2k
2
votes
1
answer
315
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 ...
- 4,049
4
votes
0
answers
118
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). ...
- 48.8k
2
votes
0
answers
163
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$ ...
- 121
0
votes
1
answer
238
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'...
- 101
1
vote
0
answers
183
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$ ...
- 410
3
votes
0
answers
231
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 ...
- 15.8k
1
vote
1
answer
97
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$-...
- 13.2k
6
votes
0
answers
296
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 ...
- 15.8k
1
vote
0
answers
128
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.
...
0
votes
0
answers
110
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 ...
- 2,089
4
votes
1
answer
193
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 ...
- 48.8k
1
vote
0
answers
113
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 ...
- 111
1
vote
2
answers
146
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$.
...
- 557
0
votes
0
answers
71
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 ...
- 1,851
7
votes
2
answers
500
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 $\...
- 1,190
3
votes
1
answer
376
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 ...
- 181
8
votes
1
answer
384
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 ...
- 1,190
5
votes
1
answer
1k
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 ...
- 181
10
votes
0
answers
626
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 ...
- 5,409
1
vote
0
answers
80
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 $${\...
- 1,851
2
votes
0
answers
44
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-...
- 13.2k
3
votes
1
answer
80
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 \...
- 149
3
votes
1
answer
177
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 ...
- 31
1
vote
1
answer
311
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'}$ ...
- 13.9k
1
vote
0
answers
61
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 ...
- 13.2k
0
votes
0
answers
26
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 ...
- 13.2k
1
vote
0
answers
123
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 \...
- 5,590
3
votes
1
answer
304
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 ...
- 1,701
4
votes
2
answers
257
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,701
3
votes
1
answer
53
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$ ...
- 48.8k
0
votes
1
answer
112
views
Weak $1$-factorizability
A simple, undirected graph is said to be $1$-factorizable if there is a partition of the edge set $E$ such that every member of the partition is a perfect matching of $G$. Let us call $G$ weakly $1$-...
- 48.8k
2
votes
1
answer
81
views
Are countable graphs with infinite minimal degree $1$-factorizable? [duplicate]
We say that a simple, undirected graph $G=(V,E)$ is $1$-factorizable if there is a partition of $E$ such that every member of the partition is a perfect matching of $G$. It is easy to see that any $1$-...
- 48.8k
11
votes
2
answers
1k
views
Proving Hall's marriage theorem using Sperner's lemma
In the paper Hall's theorem for hypergraphs (Aharoni and Haxell, 2000),
the authors prove a theorem on the existence of perfect matchings in bipartite hypergraphs, using Sperner's lemma. At the last ...
- 3,549
4
votes
2
answers
381
views
Max weighted matching where edge weight depends on the matching
Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other ...
- 367
10
votes
1
answer
2k
views
What graph's minimum vertex cover equals twice the maximum matching?
Matching: https://en.wikipedia.org/wiki/Matching_(graph_theory)
Vertex Cover: https://en.wikipedia.org/wiki/Vertex_cover
It is easy to see that
$$\texttt{minimum vertex cover} \leq 2 \texttt{ ...
- 317
1
vote
1
answer
376
views
Expanding Hall's theorem [closed]
I'm trying to get a "feel" about Hall's theorem and try to expand it for one to many matching.
So my question is:
Given a bipartite graph, what would be a neccessary and sufficient condition for that ...
- 19
1
vote
0
answers
66
views
Matching generating function of 2-lifts
Let $P_G$ denote the matching generating function of a finite simple bipartite graph $G$.
Let now $H$ be a $2$-lift of $G$. We know (see for example Proposition 5.3.3 in Barvinok's book Combinatorics ...
2
votes
2
answers
223
views
Number of subgraphs with matching of size $n$ for a complete bipartite graph
Say we have a $K_{n,n}$ bipartite graph (i.e. a complete bipartite graph with $n$ nodes on each side). We induce a subgraph by deleting some subset of edges. There are $2^{n^2}$ possible subgraphs. ...
- 41
2
votes
1
answer
55
views
maximum weighted matching with weights being sets
Given a set $S$ and a bipartite graph $G$, each edge $v\in E(G)$ covers a subset $S_v$ of $S$. My problem is to find a matching maximizing the number of covered elements, i.e., denote $V$ the set of ...
- 367
3
votes
1
answer
205
views
Does there exist an r-regular graph (r≥2) with a unique maximum matching?
Akbari, Ghodrati, Hosseinzadeh (2017), On the structure of graphs having a unique k-factor, Aust. J. Combin. (pdf) show:
... we prove that there is no r-regular graph (r≥2) with a unique perfect ...
- 1,327
5
votes
0
answers
115
views
Hypergraphs with only disjoint perfect matchings
Let $H(n,r)$ be the set of $r$-uniform hypergraph with $n$ vertices that have only disjoint perfect matchings (i.e. every hyperedge only appears in at most one of the perfect matchings). Let $m(h(n,r))...
- 155
2
votes
1
answer
321
views
Extending perfect matchings into Hamiltonian cycles
Let $G$ be a simple cubic graph which has a Hamiltonian circuit $C$. In general, it is not possible to find a second Hamiltonian circuit which contains all the chords of $C$. For example, the Wagner ...
- 1,018
0
votes
0
answers
58
views
Decomposition of triangle-free bridgeless planar cubic graphs
Question:
is it true that every triangle-free connected bridgeless planar cubic graph can be decomposed into a vertex-disjoint cycle cover and a single maximal matching of the edges that are adjacent ...
- 13.2k
5
votes
1
answer
125
views
Generalization of Menger's theorem to infinite graphs
Aharoni and Berger generalized Menger's Theorem to infinite graphs: For any digraph, and any subsets $A$ and $B$, there is a family $F$ of disjoint paths from $A$ to $B$ and a set separating $B$ from $...
- 1,644
0
votes
1
answer
150
views
Combining three matchings to form a maximal matching
Consider a regular tripartite graph $G$ with maximum degree $\Delta\ge3$ and parts $A,B,C$. Now, the induced subgraphs $A\cup B, B\cup C$ and $A\cup C$ are all bipartite.
Now, is there a way to ...
- 2,089