Questions tagged [matching-theory]
For questions about matchings in graphs.
592 questions
0
votes
0
answers
37
views
Is Exact Matching with more than two colours NP-hard?
I'm interested in the following problem: given a (multi-)graph with each edge coloured by one of 3 colours, find a perfect matching with exactly k_i edges of colour i in {1,2,3}. I'm also interested ...
- 353
3
votes
0
answers
50
views
Planted Matching in Hypergraphs
I’m working on the planted perfect matching problem in random $k$-uniform hypergraphs $k \ge 3$, and I’m stuck on rigorizing the impossibility (lower bound) side of what looks like the information-...
- 31
1
vote
1
answer
72
views
What is a worst case graph for this streaming algorithm?
Consider the following streaming algorithm for maximum matching in a weighted graph.
...
- 779
2
votes
2
answers
121
views
What is the relation between matchings and edge coverings?
Let $G$ be a graph with no isolated vertices.
A set of vertices in $G$ is called
independent if no two vertices in the set are incident on the same edge;
vertex cover if every edge is incident to ...
- 7,009
5
votes
0
answers
191
views
Does Birkhoff-von Neumann's Theorem easily imply Hall's Marriage Theorem or equivalent?
The following is a collection of combinatorics theorems commonly refereed as "equivalent" due to one being easily derived from another.
Theorem (Hall).
A finite bipartite graph $G = (A\...
- 7,009
2
votes
0
answers
24
views
Is it true that a graph has a fractional perfect matching if and only if $i(G\setminus S)\leq |S| $ for all $S\subset V(G)$?
Is it true that a graph has a fractional perfect matching if and only if $i(G\setminus S)\leq |S| $ for all $S\subset V(G)$? And why?
Here $i(G\setminus S)$ denotes the number of isolated vertices of ...
- 1,112
2
votes
1
answer
105
views
Why does $A = A^{-1}$ (adjacency matrix squared equals identity) imply that the graph is a perfect matching?
I’m studying properties of adjacency matrices of graphs.
Suppose $G$ is a simple undirected graph with adjacency matrix $A$. If we have
$$
A^2 = I,
$$
where $I$ is the identity matrix, then it seems ...
- 23
1
vote
1
answer
76
views
Randomised Algorithm for Maximum Matching
Consider the following randomised distributed algorithm for computing (constant-approximation) maximum matching. The algorithm
has $\log ∆$ iterations indexed by $i∈{0,1,2,\ldots,\log ∆−
1}$. We ...
- 43
1
vote
0
answers
54
views
Let $G$ be a countably infinite, $d$‑regular, connected, vertex‑transitive, bipartite graph. Show that $G$ admits a perfect matching.
I’m trying to prove the following statement:
Let $G$ be a countably infinite, $d$‑regular, connected, vertex‑transitive bipartite graph. Show that $G$ admits a perfect matching.
Problem
$G$ is a ...
- 103
0
votes
0
answers
73
views
Combinatorial understanding of a specific power of monomial ideals
Definition. Let $I$ be a squarefree monomial ideal (that is, an ideal in $K[x_1,\dots,x_n]$ generated by squarefree monomials). The $k$-th squarefree power $I^{[k]}$ of $I$ is the ideal generated by ...
user969954
4
votes
1
answer
112
views
Balloons in 3-Regular Graphs: Tight Bound on Their Number?
Let $G$ be a connected 3-regular (cubic) graph on $n$ vertices. A balloon in $G$ is defined as a maximal subgraph of $G$ that has no cut-edges (i.e., is 2-edge-connected) and is connected to the rest ...
- 3,613
1
vote
1
answer
86
views
Accidentally Overcounting on a Marriage Question
I've recently been reading Paul Zeitz's "The Art and Craft of Problem Solving" Third Edition, and I've come across a problem whos solution I was confused on. The problem reads,
"In a ...
- 65
0
votes
0
answers
41
views
Rounding of Linear Program for Complete Matching
The following is taken from Design of Approximation Algorithms by Williamson and Shmoys available at https://www.designofapproxalgs.com/book.pdf
Exercise 4.6 Let $G = (A, B, E)$ be a bipartite graph; ...
- 1,856
1
vote
1
answer
91
views
Perfect matching with hitting sets [closed]
Suppose, my input is a graph $G$, and $k$ sets $A_1, A_2,\ldots, A_k\subseteq E(G)$. I wish to find a perfect matching $M$ such that $M\cap A_i\neq \emptyset$, for all $i \in 1,2,\ldots, k$. Can such ...
- 107
0
votes
2
answers
117
views
Inequality for a perfect matching in a bipartite graph built from a family of sets
[Crossposted from mathoverflow]
Let $\mathcal F$ be a family of subsets of $[n]=\{1,2,\dots,n\}$. For $k \in [n]$ let $\mathcal F_k = \{A \in \mathcal F : k \in A \}$ and $\mathcal F_{\overline{k}} = \...
- 2,405