A matching is a subset of the edges of a graph, such that no edge in the subset shares a vertex with another.
1
vote
1answer
334 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 ...
13
votes
1answer
273 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 ...
3
votes
1answer
223 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 ...
0
votes
0answers
192 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 ?
5
votes
1answer
167 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 ...
12
votes
1answer
432 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 ...
5
votes
1answer
265 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 ...
19
votes
4answers
857 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 ...
2
votes
1answer
459 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
...
9
votes
1answer
307 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 ...
6
votes
1answer
257 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. ...
5
votes
0answers
475 views
Is Exact Cover by Equally-Sized Sets reducible to Multi-Dimensional Matching in a certain nice way?
This question is motivated by my other question “Gap hardness of Multi-Dimensional Cover,” which is in turn motivated by the question “Set Cover for Permutation Matrices” by Brayden Ware.
Informal ...
17
votes
1answer
619 views
Can we decide whether a permanent has a unique term?
Suppose we are given an n by n matrix, M, with integer entries. Can we decide in P whether there is a permutation $\sigma$ such that for all permutations $\pi\ne\sigma$ we have $\Pi M_{i\sigma(i)}\ne ...
19
votes
2answers
736 views
Maximum number of internally vertex-disjoint odd length s-t paths
Let $G$ be an undirected simple graph and let $s,t \in V(G)$ be distinct vertices. Let the length of a simple s-t path be the number of edges on the path. I am interested in computing the maximum size ...
9
votes
3answers
577 views
Extension to the Stable Marriage Problem ?
This may sound more like a social sciences question more than a TCS one, but it is not. When reading "Randomized Algorithms" which describes the Stable Marriage Problem, one can read the following ...
1
vote
1answer
284 views
Complexity of two perfect matchings with minimum shared edges?
Perfect Matching problem is polynomial time solvable in general graphs.
Given undirected simple graph,
Is the problem of finding two perfect matching with minimum shared edges between them ...
8
votes
4answers
952 views
Complexity of marriage matching problem?
Suppose you have $n$ males and $n$ females. Each person has $m$ attributes. Each person indicates a set of attributes that a possible candidate should have. A matching is a set of pairs. Each pair ...
