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.
92
questions
4
votes
0
answers
70
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 ...
- 173
1
vote
0
answers
51
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 ...
- 288
3
votes
1
answer
99
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
54
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
120
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
131
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, ...
- 13.9k
1
vote
1
answer
200
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
136
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
121
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
308
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
355
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
63
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 ...
- 25
2
votes
1
answer
44
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
94
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
55
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
770
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 ...
- 576
1
vote
0
answers
164
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 ...
- 607
3
votes
1
answer
168
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
144
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
323
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
270
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
126
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
210
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,227
2
votes
0
answers
76
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
338
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 ...
- 12.8k
18
votes
0
answers
545
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,227
0
votes
1
answer
91
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,299
1
vote
1
answer
104
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
47
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
590
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,367
2
votes
0
answers
66
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,367
1
vote
1
answer
80
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,438
1
vote
2
answers
877
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,723
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
371
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 ...
- 12.8k
3
votes
1
answer
109
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.3k
8
votes
2
answers
316
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 ...
- 395
4
votes
2
answers
248
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 ...
- 541
8
votes
1
answer
474
views
Bipartite matching with degree domination
Given an unweighted bipartite graph $G=(V, E)$. Is it true that there always exists a nonempty matching $M\subseteq E$ (not necessarily maximal), such that for every $(i,j)\in E$ with $i$ matched and $...
- 723
2
votes
1
answer
175
views
Maximum stable matching/allocation
I checked some papers on two-side stable allocation/matching (marriage, worker/company, doctor/hospital), but has not found any literature on the following problem. Can someone point out if I missed ...
- 119
2
votes
1
answer
304
views
Are there any results on the following "generalized matching" problems?
Given a graph $G = (V, E)$, one can view a matching $M$ on the graph as a partition of $V$ into vertex sets $S_{i, j}$ for $j \in \{1, 2\}$, where each $S_{i, j}$ induces a subgraph in $G$ isomorphic ...
- 131
0
votes
1
answer
283
views
Online/approximate weighted and capacitated bipartite matching
I wish to take a look at online/approximate weighted and capacitated bipartite matching problem.
Consider $G=\{L\cup R, E\}$, $|L|=n_1$, $|R|=n_2$, $|E|=m$ and $E\subseteq L\times R$. For each $r_i\...
- 119
10
votes
1
answer
1k
views
Maximum weight matching and submodular functions
Given a bipartite graph $G = (U \cup V, E)$ with positive weights let $f: 2^U \rightarrow \mathbb{R}$ with $f(S)$ equal to the maximum weight matching in the graph $G[S\cup V]$.
Is it true that $f$ ...
13
votes
0
answers
389
views
Consequences of bipartite perfect matching not in NL?
Are any significant consequences known of $\text{BPM} \not\in \textsf{NL}$?
I'm interested in the status of the following well-studied decision problem, in particular whether it is known to be in $\...
- 18.9k
1
vote
0
answers
119
views
Algorithm for maximum bipartite matching with arriving edges?
Given a bipartite graph with fixed nodes and incrementally arriving edges, is there any efficient algorithm to compute and update the maximum matching?
- 111
5
votes
1
answer
433
views
On Zero sum perfect matching
Fix $c\geq1$.
Input is a $m$ vertex complete graph with edges assigned $a_1,\dots,a_{\frac{m(m-1)}2}\in\Bbb Z$ in some order.
Is it $\mathsf{NP}$-complete to decide if there is a perfect matching of ...
user34945
8
votes
2
answers
3k
views
Complexity of counting matchings in a bipartite graph
I might be missing something obvious but I can't find references about the complexity of counting matchings (not perfect matchings) in bipartite graphs. Here is the formal problem:
Input: a bipartite ...
- 8,916