The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
1answer
44 views

Why is bipartite graph matching hard?

I am reading on how solving maximum flow (Ford-Fulkerson) can be also used to solve unweighted bipartite graph matching problem. I think I don't understand the essence of this problem, because to me ...
0
votes
2answers
54 views

Minimizing the overall cost over groups

I am trying to solve the problem of minimizing the overall cost over several groups. The schema of the data goes something like this: ...
0
votes
1answer
46 views

Multiple matching in Maximum Flow problem?

I'm sorry if this has already been asked before, but I couldn't find any similar questions. The situation is as such: Assume there are x restaurants, each with a capacity q, and y people, each of ...
3
votes
0answers
126 views

Online bipartite edge-cover problem with requirements

I have $N$ nodes $v_1,\ldots,v_N$ in one partition $X$ and $M \leq N$ nodes $u_1,\ldots,u_M$ in a different partition $Y$. I want to connect nodes in $X$ to nodes in $Y$ with edges under the following ...
1
vote
1answer
35 views

A condition ensuring that a bipartite graph have a perfect matching

There is a bipartite graph $G=(A,B,E)$ such that for every edge $(a,b)$ (where $a$ comes from $A$ and $b$ from $B$), $\deg(a) \geq \deg(b)$, and additionally $\deg(a) \geq 1$ for all $a \in A$. From ...
3
votes
0answers
51 views

Complexity class of a counting problem

Consider the following inequalities: $\sum_j a_{ij}x_{ij}=1 \;\;\; i=1,...,n$ $\sum_i a_{ij}x_{ij} \le y_i \;\;\; j=1,...,n$ $x_{ij} \ge 0 \;\;\; i,j=1,...,n$ $y_i \in \{0,1,2\} \,\,\,\, i=1,...,...
1
vote
1answer
72 views

Match students and teachers based on ranking

I have a similar question to that of Stable Marriage Problem. This is the criteria1) 1 Student must have 1 Teacher only.2) 1 Teacher ideally should have 3-4 Students. The spreadsheet is done using ...
0
votes
0answers
27 views

Search maximal matching in a non-bipartite graph

Given a G(V,E) graph and we want find a maximal matching. If it is a bipartite graph, there is the Hungarian method can solve this problem. But how can I solve the problem if it is a non-bipartite ...
2
votes
2answers
125 views

Is there a name/algorithm for this problem related to set cover and CSP?

Our college would like to determine if a transcript contains classes that satisfy every general education requirement. What makes this nontrivial is that while a single class may in theory satisfy ...
3
votes
1answer
104 views

Maximum bipartite matching with extra reward for covering certain sets

Consider the following variation of Bipartite Maximum Matching. As usual, we have a bipartite graph $G$. In addition, there is an additional collection of sets $S_1,S_2,\dots,S_k$, with each set $...
4
votes
1answer
44 views

Why is bipartite perfect matching a special case of clique problem?

In Lovász writes [1] : bipartite graph has a perfect matching, which is a special case of the clique problem Why is bipartite perfect matching a special case of clique problem? The Work of A....
2
votes
1answer
641 views

Perfect matching in a graph and complete matching in bipartite graph

When I google for complete matching, first link points to perfect matching on wolfram. It defines perfect matching as follows: A perfect matching of a graph is a matching (i.e., an independent ...
1
vote
0answers
63 views

How can we add back edges in Ford - Fulkerson algorithm?

I was going through the Ford-Fulkerson(FF) algorithm. The given graph is directed and there is an edge from A to B with capacity y. Now sending a flow of x units (x < y) from A to B is equivalent ...
2
votes
0answers
40 views

Min-weight bipartite matching in Christofides' algorithm

Content: The Christofides algorithm finds a minimum spanning tree, then finds all the odd degree vertices, and adds extra edges using a minimum weight bipartite matching on those odd vertices to make ...
2
votes
1answer
147 views

Finding a minimum weight perfect matching in Christofides TSP algorithm

Context: After creating the minimum spanning tree, the next step in Christofides' TSP algorithm is to find all the N vertices with odd degree and find a minimum weight perfect matching for these odd ...
3
votes
2answers
197 views

Maximum bipartite matching when some nodes must be matched

Consider the problem of finding a maximum cardinality bipartite matching under the additional condition that some set $S$ of nodes (all lying on the same side of the bipartition) must be matched. ...
9
votes
0answers
182 views

How fast can we compute the size of maximum matching in an unweighted bipartite graph?

Is there a way to compute the size of a maximum matching in an unweighted bipartite graph more efficiently (e.g. faster) than computing a maximum matching? It is a long shot but it is often ...
2
votes
1answer
55 views

Computing optimal assignments using little memory

I have two lists where each item in the first list has a rating for each item in the second. I need to determine an optimal matching (or the best x scenarios) where items are matched, but each item ...
1
vote
1answer
94 views

Why is one traversal sufficient for the Kuhn's maximal matching problem algorithm?

In Kuhn's algorithm for the maximum bipartite matching problem we iterate through the vertices of one partite set and try to build the increasing chain, starting with the current vertex. Once the ...
2
votes
1answer
28 views

About having analytic control over any algorithm which finds perfect matchings.

A trivial algorithm to decompose a degree-d (n,n)-bipartite graph into d disjoint perfect matchings is this : direct all the edges from left to right and put capacity one on each of them - then add a ...
1
vote
0answers
46 views

Stable matching of producers, consumers and objects

Has the following version of the stable matching problem been studied? There are $k$ types of objects. There are $n$ producers, each of whom can produce a single object of any type, and has a ...
3
votes
1answer
924 views

Find perfect matching whose weight is minimal, in polynomial time

Given a bipartite graph $G=(A,B,E)$ and a weight function $w: E \rightarrow\mathbb{R}^+$, I'd like to find a perfect matching $M\subseteq E$ with min. weight. I'm assuming $|A| \leq |B|$, and WLOG $G$ ...
4
votes
1answer
107 views

Term for a matching which is perfect on one side only

What is a standard term for a matching in a bipartite graph, in which one part has less vertices than the other part, and the part with less vertices is fully matched (but the other part is, obviously,...
5
votes
1answer
92 views

Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph?

Usually questions deal with claw-free graphs, but suppose we are given a graph $G$ and there are $k$ vertex-disjoing claws in the graph, how can we derive a randomised algorithm using color coding to ...
4
votes
2answers
185 views

Vertex cover in bipartite graph from Hopcroft-Karp Algorithm

Vertex cover in bipartite graph is polynomial algorithm: by König's theorem the number of edges in a maximum matching is the number of vertices in a minimum vertex cover. I've implementated the ...
2
votes
2answers
148 views

Union grouping in bipartite graphs?

I'm trying to figure out a good (and fast) solution to the following problem: I have two roles I'm working with, let's call them players and teams having many-to-many relationship (a player can be on ...
2
votes
1answer
622 views

Stable marriage problem with only one side having preferences [duplicate]

I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and ...
3
votes
1answer
140 views

Finding a subset in bipartite graph violating Hall's condition

We are given a bipartite graph of $n \leq 200$ vertices in both the first and the second partite set. Let $U$ be some set of vertices in the first set, and $V$ those vertices from the second that are ...
1
vote
0answers
131 views

Finding the number of distinct maximal matching in a bipartite graph [closed]

In a bipartite graph, how can we find the total number of ways of getting a maximal matching? The cardinality of both the sets in the bipartite graph may not be the same. So two matchings are said to ...
6
votes
1answer
302 views

Complexity of Hopcroft-Karp

I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where ...
4
votes
1answer
82 views

Decomposing a bipartite graph of maximal degree d to d matchings

I have tried for the last few days to prove that any bipartite graph of maximal degree d may be broken into (at most) d matchings. My main approach is to prove this inductively over the maximal ...
0
votes
3answers
117 views

Bipartite Matching in the Plane

I'm currently working on a problem that I came across: You are given a set $B$ of $n$ points in the plane, and a set $R$ of $n$ points in the plane. Each point is given by its coordinates. I have ...
1
vote
2answers
939 views

Concrete and simple applications for bipartite graphs [closed]

I am looking for concrete and simple problems that may be solved using bipartite graphs or bipartite graph properties. Any idea along with explanations are welcome.
2
votes
1answer
83 views

Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths

Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut (...
1
vote
1answer
30 views

The min cut capacity in a network based on a bipartite graph (Hall's Theorem)

Thanks to Yuval Filmus, I got to read these lecture notes by Trevisan. At the bottom half of Page 5, The capacity of cut $S$ is the number of edges that go from $S$ to $\overline{S}$, that is $\...
2
votes
1answer
65 views

How to optimally seperate a student body?

Students will identify certain students they want to work with. I have therefore decided to split them into two groups where I want to minimize the number of people in Group 1 who want to work with ...
1
vote
1answer
285 views

maximum bipartite matching

I am working out with the rooks problem. If there are m rooks on an nxn chessboard,i have to give describe a polynomial (in m and n) time algorithm that finds a maximum-sized subset of the rooks such ...
5
votes
3answers
336 views

Maximum number of matched vertexes in a one-to-many bipartite graph

I have a variant of bidding problem at hand. There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who ...
1
vote
0answers
35 views

How to maximize the number of buyers in a shop?

There is a shop which consists of N items and there are M buyers. Each buyer wants to buy a specific set of items. However, the cost of all transactions is same irrespective of the number of items ...
1
vote
1answer
118 views

Local search: Problem with neighborhood definition

I have question on understanding the following neighborhood relation within a local-search approximation scheme. Let $M$ be a legal matching on any bipartite graph. Let $U_k$ be the neighborhood ...
0
votes
0answers
327 views

Hopcroft–Karp algorithm time complexity

In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph: https://dl.dropboxusercontent.com/u/64823035/04569670.pdf The ...
3
votes
3answers
597 views

Number of ways to fill a 2xN grid with M colors

This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri. In short, the question asked to find the number of ways to fill a $ 2\times N$ grid with $M$ colors such that no two ...
2
votes
1answer
77 views

Number of Matchings in a Bipartite

Given two sets A and B of sizes |A| = n and |B| = m, where m >= n. There are edges from set A to set B. I need to find the number of matchings where all of vertices ...
4
votes
2answers
367 views

Bipartite Graph Game

So say we have a bipartite graph G=(X,Y,E). Let's make a game out of it. I go first. I pick a node in X. You go next. You pick a node in Y that is connected by an edge to the node I picked. Next it's ...
5
votes
2answers
322 views

In the Hopcroft-Karp algorithm, what is the purpose of the breadth first search?

In the Hopcroft-Karp algorithm for bipartite matching, I don't understand the purpose of the breadth first search. I think it's used to find a set of vertex disjoint augmenting paths, but I'm not ...
3
votes
1answer
872 views

Existence of bipartite perfect matching

Let $B = G(L, R, E)$ be a bipartite graph. I want to find out whether this graph has a perfect matching. One way to test whether this graph has a perfect matching is Hall's Marriage Theorem, but it is ...
3
votes
1answer
313 views

Assignment problem with no cost

I have a problem that I was able to conceptualize as following: Problem We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination ...
5
votes
1answer
2k views

How to find the maximum independent set of a directed graph?

I'm trying to solve this problem. Problem: Given $n$ positive integers, your task is to select a maximum number of integers so that there are no two numbers $a, b$ in which $a$ is divisible by $...
4
votes
1answer
113 views

Bipartite graph question

Assume you are given a bipartite graph $G = (U, V, E)$ and you are given an integer $n$. Assume also that for each $v \in V$, you are given two integers $v_{min}$ and $v_{max}$ (where $v_{min} \le v_{...
0
votes
1answer
116 views

Graph Bipartiteness

I have 2 questions regarding Bipartiteness with corresponding examples. 1) Can a non-connected graph be bipartite if it has an isolated vertex? Let's take the following graph: I would say YES with ...