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

learn more… | top users | synonyms

0
votes
0answers
28 views

Bipartite matching with constraint: match at least one node of each subgroup

This problem is derived from "How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph?" by adding an additional constraint: each vertex belongs to ...
1
vote
0answers
34 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?
6
votes
1answer
265 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 ...
7
votes
2answers
234 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 ...
0
votes
0answers
40 views

How to find all alternating cycles wrt. a perfect matching?

Given an undirected graph $G$, Tarjan's bridge finding algorithm gives me the set of all bridges (edges that do not occur in any cycle) in $G$ in linear time. Now, I have a perfect matching $M$ in ...
1
vote
1answer
50 views

Approximations for the Stable Fixtures Problem

I have a set of N items, each with a subset of those items they can be paired with; each pair has a weight. I'd like to choose pairs to maximize the total weight, subject to each item being in at ...
14
votes
2answers
579 views

How many negations do we need to compute monotone functions?

Razborov proved that the monotone function matching is not in mP. But can we compute matching using a polynomial size circuit with a few negations? Is there a P/poly circuit with $O(n^\epsilon)$ ...
-3
votes
1answer
152 views

Weighted matching algorithm for minimizing max weight

Consider the following matching problem: Input: a complete weighted bipartite graph with $n+m$ vertices, given by $n$, $m$, and $w_{i}$ a permutation of $[m]$ for each $i \in [n]$. Output: a ...
2
votes
1answer
114 views

Perfect Matching with ``set-over-like" constraints?

Problem Description: Let k and n be some natural numbers. We are given a complete bipartite graph G where each side of G has n vertices. G is edge-labeled with labels being subsets of {1,...,k}. We ...
4
votes
1answer
71 views

Approximate matching in table of integer vectors

Disclaimer: This is my first question on cstheory.stackexchange.com so please be forgiving. I have a list of M (M is big, more than 1 million elements) vectors of integers. Each vector can contain ...
-2
votes
2answers
82 views

Is there a typo in this definition of Minimal Maximal Matching [closed]

in the following paper http://journal.frontiersin.org/article/10.3389/fphy.2014.00005/full the author describes the minimax problem as follows: Given a graph G = (V, E), we are looking for a ...
4
votes
0answers
77 views

Graph factors of maximum weight

I am trying to find references to a weighted version of the graph factor problem for the case when the "target degree" is a set of integers with "gaps" of size at most one. The unweighted version of ...
5
votes
1answer
253 views

Assignment problem with multiple workers for each job

I am wondering if there are any results on the following version of the assignment problem. We are given a set of jobs $J$ and a set of workers $W$, and for each job $j$ and worker $w$ we are given ...
1
vote
1answer
173 views

Is finding whether k different perfect matchings exist in a bipartite graph co-NP?

Few definitions first. The co-NP problem is a decision problem where the answer "NO" can be verified in polynomial time. The perfect matching in a bipartite graph is a set of pairs of nodes (a pair is ...
5
votes
1answer
190 views

Matching problems that are easy for bipartite graphs but hard for general graphs

Are there variants of matching problem (decision or optimization problem) that are polynomial time solvable for bipartite graphs but are NP-hard for general graphs?
7
votes
0answers
139 views

Maximum weight “fair” matching

I'm interested in a variant of the maximum weight matching in a graph, which I call "Maximum Fair Matching". Assume that the graph is full (i.e. $E=V\times V$), has even number of vertices, and that ...
2
votes
1answer
511 views

Modifying Hopcroft-Karp algorithm to get approximate bipartite matching

I am trying to find an algorithm to find an $\epsilon$-approximate maximum matching $M_{\epsilon}$ in a bipartite graph in $O(m/\epsilon)$. The partite groups are of equal size, they are $A$ and $B$. ...
0
votes
1answer
145 views

Graph theory: definiton of the crown of a graph

I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand: A crown of a ...
8
votes
0answers
351 views

Is it possible to solve perfect matching in linear time

As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft. Is it possible to solve perfect matching problem in linear time for given ...
5
votes
1answer
212 views

Is there an extension to the stable roommates problem with multiple roommates per room?

The stable roommates problem presents a set of N two-person rooms and 2N would-be roommates with preferences over each other, and asks for a stable allocation of roommates to rooms (and, really, to ...
7
votes
2answers
150 views

Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?

The $q$-Dimensional $p$-Matching is defined as follows: Given disjoint universes $U_1,\ldots,U_q$, think of an element in $U_1\times\ldots\times U_q$ as a set that contains exactly one element from ...
8
votes
1answer
568 views

Fast algorithm for weighted bipartite matching problem

I have a set of $n$ agents and a set of $n$ tasks, and I need to assign each agent to exactly one task such that a cost is minimised. Some agents are incompatible with some tasks. I have an ...
4
votes
3answers
162 views

Another algorithm for stable matching?

The only algorithm I have seen to compute a stable matching is the one by Gale an Shapley. Is there any other algorithm to compute a stable matching?
2
votes
0answers
350 views

Christofides algorithm for directed graph

Is it possible to implement the Christofides algorithm for an directed Graph? Suppose you have an undirected Graph, in which every vertex has an edges in both ways to every other in the graph (not to ...
2
votes
0answers
47 views

Hungarian Search and min net-cost-length paths

Consider the Hungarian Search algorithm for max/min weighted bipartite matching. Let G be a bipartite graph weighted by $w:E\rightarrow\mathbb{R}$ and let $M$ be a matching in $G$, let $S$ be a subset ...
3
votes
1answer
395 views

Subset of a bipartite graph with maximal number of minimal unmatched vertices

Given a bipartite graph $G = (U \sqcup V, E)$ with sets of vertices $U$ and $V$ and edge set $E \subseteq U \times V$, a matching $M$ is a subset of $E$ whose edges have no common vertices: for all ...
2
votes
1answer
389 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 ...
10
votes
1answer
224 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 ...
13
votes
3answers
543 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 ...
0
votes
1answer
514 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 ...
4
votes
1answer
148 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 ...
1
vote
1answer
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 ...
14
votes
1answer
343 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 ...
4
votes
1answer
549 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 ...
1
vote
0answers
235 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 ?
6
votes
1answer
337 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 ...
14
votes
1answer
527 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
363 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 ...
20
votes
4answers
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 ...
2
votes
1answer
557 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 ...
11
votes
1answer
429 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
323 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. ...
7
votes
0answers
772 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 ...
16
votes
1answer
691 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 ...
18
votes
2answers
1k 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 ...
10
votes
3answers
937 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
362 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
2k 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 ...