# Tagged Questions

A matching is a subset of the edges of a graph, such that no edge in the subset shares a vertex with another.

31 views

36 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?
284 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 ...
311 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 ...
41 views

420 views

### Approximate Maximum Weight Matching

I am looking for an approximated (or randomized) maximum weight matching algorithm. Do you have any suggestion for me? In my problem, I have a bipartite graph with N abound 1000 (#vertices on each ...
226 views

### Monotone bijections between lists of intervals

I have the following problem: Input: two sets of intervals $S$ and $T$ (all endpoints are integers). Query: is there a monotone bijection $f:S \to T$? The bijection is monotone w.r.t. the set ...
547 views

### Complexity of topological sort with constrained positions

I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$. A topological sort of $G$ is a bijection $f$ from the vertices ...
564 views

### “k-matching” in graphs [duplicate]

A matching in a graph is a set of edges that are pair-wise non-adjacent. IOW, each node involved in the matching appears in only one edge. Now I am wondering is there a generalized'' concept of ...
150 views

### Perfectly matchable edges in a bipartite graph

Consider the following problem: Given a bipartite graph $G = (V, E)$, an unmatched edge is one that does not appear in any perfect matching. Design an algorithm to find all unmatched edges. (assume |...
2k views

### Reducing a minimum cost edge-cover problem to minimum cost weighted bipartie perfect matching

I have a set of edges [m,n] of a bipartie graph U, V with a cost assigned to each edge and I need to find the minimum cost edge-cover covering all nodes in U, V. There is one additional constraint is ...
345 views

### Is it enough for linear program constraints to be satisfied in expectation?

In the paper Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching, while proving that the RANKING algorithm is $\left(1 - \frac{1}{e}\right)$-competitive, the authors show that the ...
580 views

### Matching on bipartite graph - multiple edges

I have a weighted bipartite graph consisting of two sets $S$ and $P$. ($|S| > |P|$). I need to find a matching so that every node $s$ in $S$ matches a node of $P$. But a node $p$ in $P$ can match ...
239 views

### Perfect fractional matching of uniform hyper graph

Are there necessary and sufficient conditions for a uniform hyper graph to have a perfect fractional matching ?
338 views

### In a random perfect matching of a regular bipartite graph, are all edges equally probable?

Consider a d-regular bipartite graph G, for d>=1. Obviously, G contains a perfect matching. Consider a perfect matching M in G chosen uniformly at random from all perfect matchings in G. Is it the ...
530 views

### Perfect matchings in a chessboard?

Consider the problem of finding the maximum number of knights that can be placed on a chessboard without two of them attacking each other. The answer is 32: it's not too difficult to find a perfect ...
375 views

### Bipartite maximum matching size from eigenvalues

Supposing we know the adjacency matrix $\mathcal{A}_{G}$ of a given regular (or irregular) bipartite graph $G$. Are there good lower and upper bounds to the size of maximum matching from the graph's ...
2k views

### What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the ...
560 views

### Matching algorithm

I'm writing an application which divides a population of users into pairs for the purpose of performing a task together. Each user can specify various preferences about their partner, e.g. gender ...
430 views

### Improved lower bound on monotone circuit complexity of perfect matching?

Razborov proved that every monotone circuit that computes the perfect matching function for bipartite graphs must have at least $n^{\Omega(\log n)}$ gates (he called it "logical permanent"). Has a ...
324 views

### A decomposition theorem for maximum weight matchings

The following paper presents a way to solve the maximum weight matching of a bipartite graph by reducing it to computing maximum weight matchings of two lighter bipartite graphs: M.-Y. Kao, T. W. Lam,...