# 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
Filter by
Sorted by
Tagged with
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 ...
1 vote
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 ...
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
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 ...
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:...
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, ...
1 vote
200 views

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 ...
50 views

144 views

1 vote
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 ...
545 views

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 ...
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 ...
474 views

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$ ...
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 $\... 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? 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 ... 