Questions tagged [matching]
A matching is a subset of the edges of a graph, such that no edge in the subset shares a vertex with another.
101
questions
2
votes
0
answers
138
views
Counterexample for the 1-optimal matching algorithm in Gabow's and Tarjan's paper on scaling algorithms for networks
Context
I am reading Faster scaling algorithms for network problems by Gabow and Tarjan where I am researching part 2: "Matching and extensions". However, I am a bit confused with the ...
- 21
0
votes
0
answers
20
views
What is a tight set for a face $F$ of the perfect matching polytope
I was reading the paper The Matching Problem in General Graphs is in Quasi-NC - Ola Svensson, Jakub Tarnawski. There the word mentioned in many places for example Definition 4.1 `$S$ is tight set for ...
- 280
0
votes
0
answers
36
views
Enhancing a bipartite perfect matching solution with 1-to-2 matchings
We're doing hobby events where people list their items followed by a wishlist of what they would like to receive in exchange for each one of their items, then the current algorithm finds the biggest ...
2
votes
2
answers
108
views
Weighted bipartite matching with no-cycle constraint
Given a weighted bipartite graph, I need to find a maximum-weight matching with the following additional constraint: the residual graph of the chosen matching is not allowed to contain any cycles. By ...
- 233
1
vote
0
answers
89
views
Development details of the Hungarian algorithm for Maximum Perfect Bipartite Matching
There are two realization forms of Hungarian algorithm. One is the original dynamic matrix, and the other is via equality subgraph. I just checked the original paper of Hungarian method by Kuhn, which ...
2
votes
1
answer
113
views
Constrained Bipartite Matching
Let $G = (X,Y,E)$ be a bipartite graph. For some $A \subseteq X$ we say that $A$ can be perfectly matched if there is a matching $M \subseteq E$ such that all vertices in $A$ are matched; that is, for ...
- 412
0
votes
0
answers
47
views
Bipartite Matching with a Partition Constraint over the Vertices
Let $G = (X,Y,E)$ be a bipartite graph and let $X_1,\ldots,X_r$ be a partition of $X$.
For some $i \in \{1,\ldots, r\}$ and $E' \subseteq E$ we say that constraint $X_i$ is covered by some $E'$ if ...
- 412
2
votes
1
answer
41
views
Find the weighted perfect "1-to-k" matching algorithm with minimum aggregated k max weight
Similar with Weighted matching algorithm for minimizing max weight. Consider the following matching problem:
Input: a complete weighted bipartite graph with $n+(k*n)$ vertices, given by $n$, $k*n$, ...
- 33
0
votes
0
answers
52
views
On a modular inverse graph construction
Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ ...
- 13.1k
4
votes
0
answers
78
views
distinguishments between query complexity of membership oracles and standard time complexity
Many combinatorial optimization problems can be described as follows. We are given a set system $(E,I)$, where $I \subseteq 2^E$ and a weight function $w: E \rightarrow \mathbb{N}$. The goal is to ...
- 412
1
vote
0
answers
64
views
Pfaffian orientation algorithm for planar graphs
I was studying finding a pfaffian orientation of a planar graph in $NC$. In Vazirani's Paper on NC Algorithms for Computing the Number of Perfect Matchings in $K_{3,3}$-Free Graphs and Related ...
- 280
3
votes
1
answer
117
views
Maximum cardinality matching on DAGs
A question on computational complexity and graph theory. The problem of finding maximum cardinality matchings of undirected graphs (the largest selection of edges such that each vertex is "...
1
vote
0
answers
56
views
Approximation algorithm for non-bipartite Euclidean matching
What is the current best (in terms of running time) (1+\epsilon)-approximation algorithm (both randomized and deterministic) for non-bipartite Euclidean (in higher dimension) matching? There are ...
- 11
3
votes
1
answer
128
views
"Market" intuition for the dual of the max-weight matching LP
I recently learned about the Hungarian algorithm for maximum-weight matching in bipartite graphs and the "market" interpretation of the primal and dual LPs. (See also these notes.)
The setup:...
- 235
2
votes
1
answer
134
views
Maximum weight matching with surreal weights
Is there an efficient algorithm for finding a maximum weight matching in a graph where the weight of each edge is a surreal number?
I strongly remember thinking about this problem about 20 years ago, ...
- 14.1k
1
vote
1
answer
353
views
Number of stable matchings
In the stable marriage problem, is it possible to find an instance with $2^{n -1}$ stable matchings when $n$ is a power of 2 (or just even)? If yes, how? I know how to build an instance in which $2^{n/...
- 113
3
votes
1
answer
146
views
Approximative counting of matchings in a graph
The work by Jerrum & Sinclair (1989) describes an approximative approach to determining the number of matchings $|M_\ast(G)|$ in a graph $G=(V,E)$. The fundamental ingredient of the approximation ...
- 139
-1
votes
1
answer
166
views
Unweighted bipartite $b$-Matching
Consider the following problem, of which I am pretty certain that it is polynomially solvable.
Given some arbitrary bipartite Graph $G=(L\cup R,E)$ and some vector $b\in\mathbb{N}^{|L|}$ with $\sum_{i=...
9
votes
1
answer
334
views
Does Horn SAT (Horn formula in CNF) have an integral polytope?
In some ways, my question is related to this: Is the matching polytope integral?
Matching and Horn-SAT are both polynomial time solvable.. So I wonder if there is a Horn polytope, similar to the ...
- 123
0
votes
0
answers
50
views
Is p-dimensional matching with (p−1)n edges NP-hard? What about 3n edges?
Let $p≥3$ an integer. I am wondering whether or not the following problems are NP-hard or not (and if they are, I am looking for a convincing argument, or even better a detailed proof):
Let $V_1,\...
10
votes
0
answers
375
views
Finding uniformly random perfect matching of a graph
Problem: Suppose that we have a graph $ G $ which admits at least one perfect matching. I would like to know if there is an algorithm that allows to find any perfect matching of this graph uniformly ...
- 121
0
votes
1
answer
68
views
Do such instances always admit a 3D matching?
I want to know whether the following kinds of special instances of the 3D Matching problem are ``yes" instances, i.e., admit a 3D matching.
We are given 3 sets $A,B,C$ containing $m$ elements ...
- 15
2
votes
1
answer
52
views
Maximum weight matching with classes of edges in a multi-edge bipartite graph
Posted a similar question in mathoverflow, have tried to reduce this to Ford Fulkerson, but been stuck. Thought I'd ask TCS community to see if there are any ideas from individuals, here.
Consider a ...
- 23
2
votes
0
answers
99
views
Is there an approximation algorithm for the three-person stable roommates problem? [closed]
While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the threesome roommates problem, is NP-...
- 121
3
votes
0
answers
58
views
Counting subsets of bipartite graph part which admit an induced perfect matching
Given a bipartite graph $G=(U \sqcup V, E)$, count $U^\prime \subseteq U$ for which $\exists V^\prime \subseteq V$ such that the induced subgraph $G[U^\prime \sqcup V^\prime]$ contains a perfect ...
13
votes
1
answer
1k
views
Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
In this talk at the Simons Institute, Holger Dell notes that there is a parsimonious reduction from 3-SAT to the 3-dimensional Matching (3-DM) problem. In other words, there is a reduction between ...
- 686
1
vote
0
answers
167
views
Is the matching polytope integral?
In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf
they prove the integrality of the matching polytope using the integrality of the perfect matching polytope.
The ...
- 649
3
votes
1
answer
218
views
3-dimensional matching variant
In the normal version of the matching problem, we are given a set of vertices $X$, $Y$, and $Z$, each of size $n$, and a set of edges $E\subseteq X\times Y\times Z$. We need to find a matching $M\...
- 33
3
votes
1
answer
147
views
What is the complexity of this weighted b-edge matching problem?
I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem:
Input: An undirected multigraph $G = (V, E)$ without
loops, an edge partition $(E_1,...
- 33
-1
votes
2
answers
366
views
Hospital Resident Matching Algorithm with Incomplete Preferences
Consider a set of doctors $D$ and hospitals $H$ such that each doctor $d \in D$ has a rank ordered strict preference over a subset of hospitals, $H_d \subseteq H$. Similarly, each hospital $h \in H$ ...
- 11
6
votes
1
answer
275
views
The asymptotic behavior of a recurrence related to stable matchings
I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows:
$$a_1 = 1, a_2 = 2$$
$$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$
Apparently, Knuth was able to prove that ...
- 205
0
votes
0
answers
139
views
Matching of two weighted graphs allowing one-to-many mapping
I am looking for a heuristic for a graph matching problem as follows.
Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
- 1
2
votes
0
answers
96
views
Alternative criterion for approximate maximum-weight perfect matching algorithms
I have asked this question in cs.stackeschange, and it was recommended to me that I asked it here.
Is there any literature on approximate maximum-weight perfect matchings where the approximation ...
- 29
6
votes
0
answers
218
views
Counting matchings on 3-regular bipartite graphs
What I call a graph here allows parallel edges.
Is the following problem #P-hard:
INPUT: a 3-regular bipartite graph $G$
OUTPUT: the number of matchings of $G$.
It is known that counting matchings ...
- 1,431
2
votes
0
answers
77
views
Hardness result or reference for a set partition problem
I'm wondering if the following problem is (or has been proven to be) NP-Complete.
Input: integer $n\ge0$, set $S_1,S_2,\ldots,S_{2n}$, set $T_1,T_2,\ldots,T_n$.
Accept iff: there exists $\{a_i,...
- 101
1
vote
0
answers
367
views
Does simplex algorithm run in polynomial on Bipartite Perfect matching polytope?
It is well known that simplex algorithm runs in exponential time in worst case.
However are there situations (necessary and sufficient conditions) where simplex algorithm runs in polynomial time?
In ...
- 13.1k
18
votes
0
answers
562
views
Perfect matching of monotone Boolean function with null Euler characteristic
For a set $V = \{0,\ldots,k\}$ of variables, let $\mathbf{G}_V$ be the undirected graph with set of vertices $\{S \subseteq V\}$ and set of edges $\{\{S,S'\} \mid S \subseteq S' \text{ and }|S'| = |S|+...
- 1,431
0
votes
1
answer
95
views
Counting sum of parities of cycle covers in cubic, planar, bipartite graphs
Let $G$ be a cubic (i.e. every degree exactly three), planar, bipartite graph. By Hall's theorem its edges can be partitioned into three perfect matchings. Take any such partition $M_0,M_1,M_2$ and ...
- 2,327
1
vote
1
answer
105
views
Algorithm for K-best NON perfect bipartite matchings
I was reading this great article: https://core.ac.uk/download/pdf/82129717.pdf
It solves a generalization of the maximum sum assignment problem by finding the k best assignments and not only the best....
- 129
1
vote
0
answers
48
views
Optimally fair stable matching
There's a nice post by Gil Kalai which outlines the inherent bias in stable matching algorithms quantitatively.
In the traditional loyd shapeley algorithm for $n$ men and $n$ women, given randomly ...
- 369
8
votes
2
answers
649
views
Min weight perfect matching with even number of red edges
Consider a weighted graph with some red edges.
We are interested in finding a perfect matching, such that the number of red edges is even, and under the previous constraints, the weight is minimized.
...
- 4,509
2
votes
0
answers
67
views
For each edge, find a matching that containing it and has maximum weight
Given a weighted graph $G=(V,E)$. For each edge $e\in E$, we are interested in finding a maximum weight matching over all matchings that contains edge $e$.
If $G$ is bipartite, then this can be done ...
- 4,509
1
vote
1
answer
86
views
Does the following 2-rounds distributed algorithm approximates a maximal matching well?
Let $G$ be an undirected graph.
I'm looking for a two-rounds distributed algorithm that matches as many vertex pairs as possible.
Consider the following protocol for vertex $v$.
Use a fair coin to ...
- 9,488
1
vote
2
answers
962
views
Is perfect matching for bipartite graph with no cycles unique?
Given a balanced bipartite graph that satisfies Hall's theorem (is non singular) then it shown that it has at least one perfect matching.
My question is if the balanced bipartite graph is also ...
- 155
11
votes
2
answers
364
views
Maximum matching M with the condition G[M] is 2K_2-free
Is there anything in the literature close to the following problem:
Given a bipartite graph $G(V,E)$ with balanced bipartition $ \{U,W\}$ , does there exist a perfect matching $ M $ in $ G $ such ...
- 1,827
4
votes
0
answers
1k
views
Optimizing Maximum Weighted Matching (Edmonds Blossom)
Background:
I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java:
https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java
The original Python implementation ...
- 231
4
votes
1
answer
400
views
Is Permanent $+$-reducible?
Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$.
Is ...
- 13.1k
3
votes
1
answer
121
views
Almost regular subhypergraph of hypergraph with large minimal degree
I am interested in knowing whether the following conjecture is true or not:
For every $d \geq 1$ there exist constants $\delta,M_0 > 0$ such that the following holds for all $M \geq M_0$.
Let $\...
- 14.5k
9
votes
2
answers
338
views
What is the connection between moments of Gaussians and perfect matchings of graphs?
Today, I heard the following statement in a talk:
The 4th moment of a $1$-dimensional Gaussian distribution with mean $0$ and variance $1$ is the same as the number of perfect matchings of a ...
- 405
4
votes
2
answers
265
views
Complexity of Uniform Generation of Perfect Matchings
Jerrum,Valiant and Vazirani on their paper "Random generation of combinatorial structures from a uniform" (http://www.cc.gatech.edu/~vazirani/AppCount.pdf) talk about seeing problems related to ...
- 561