# 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
Filter by
Sorted by
Tagged with
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
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 ...
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 ...
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
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 ...
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
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
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
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
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
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 ...
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
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
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
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
353 views

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

• 33
147 views

• 101
1 vote
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
562 views

• 14.5k
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