## Bipartite graphs with min weights

I have a full bipartite graph with node sets $$A=\{a_1,a_2,\ldots,a_n\}$$ and $$B=\{b_1,b_2,\ldots,b_n\}$$. Each node has a weight, $$v_i$$ for $$a_i$$ and $$w_i$$ for $$b_i$$. Each node $$a_i$$ is connected to exactly one node of $$B$$, say $$b_j$$, via an edge $$e_i$$, whose weight is $$\min(v_i,w_j)$$. Now I want to find a one-to-one mapping from $$A$$ to $$B$$, whose sum of edge weights is as small as possible.

My idea is to sort $$v_i$$s increasingly and $$w_i$$s decreasingly and then find the sum of all $$\min(v_i,w_i)$$ after sorting. Is it correct? Can you give a proof/disproof?

## How to find the shortest even length cycle in a bipartite graph?

If you have n vertices and m edges, how would you find the shortest cycle of a bipartite graph in O(n^2) time? To do it in O(nm) time, it is simply a BFS on every single vertex. I do not understand how you can do it just by going over every single vertex. I know you would have to stop at non-tree edges to do so, but how would you use this type of technique to guarantee this runtime and find the shortest cycle? Could anyone give me some sort of advice or help?

## Bipartite Graph in a Digraph

How do you find a sub-digraph in a digraph such that the in degree and out degree of each vertex is 1. My professor told in the class that an algorithm can be build for it using bipartite matching but I have not able to do so. I am just looking for hints on how to proceed because I am kind of stuck on where to start.

## Perfect Matching in Bipartite Graph with mutually exclusive edges

Problem

I would to solve Perfect Matching in Bipartite Graph Problem where some edges are mutually exclusive.

Example

Left vertices: $$a,b,c$$

Right vertices: $$x,y,z$$

Edges: $$(a,x),(a,y),(b,z),(c,y)$$

Exlusive pairs: $$(b,z)$$ and $$(c,y)$$

Question

Is the problem in P or NP?

Solution Attempts

I know that Perfect Matching in Bipartite Graph Problem is in P. But I cannot find a polynomial-time algorithms for the above version of this problem. I have also tried proving that it is NP, but without any luck.

## Restoring the minimum vertex cover on bipartite graph from the maximum matching

I had to solve a problem on finding the minimum vertex cover on a bipartite graph, and I used the Kőnig’s theorem and reduced it to maximum matching problem on bipartite graph, which is easily solvable, however I’m not sure how to find the actual minimum vertex cover from the edges I have. I easily get the size, however I’m not sure how to find the exact vertices in the minimum vertex cover.

## Algorithm for b-matching on bipartite graph [duplicate]

I have a bipartite graph, where I want to assign nodes in Left set to Right set of nodes. There is a “b” constraint, which limits the maximum possible node degrees on the Right set. Since it is a classic problem, I expected to find a lot of algorithms on it, but was not successful. Any ideas how to solve it?

## Maximum matching in a bipartite graph

Given a bipartite graph $$G=(V_1 \cup V_2, E)$$ and a set $$V’ \in (V_1 \cup V_2)$$. What is the complexity of finding a maximum matching in $$G$$ that uses only $$x$$ vertices from $$V’$$?

## Bipartite Planar Graph Isomorphism

I want a hueristic algorithm for the following problem. Here, $$V(G)$$, $$E(G)$$ respectively refer to the vertex set and edge set of a graph $$G$$.

Input: two planar bipartite graphs, $$G,H$$ and a map $$\phi: A\to V(H)$$, where $$A$$ is a subset of $$V(G)$$.

Task: determine if there is a (bijective) map $$\phi’: V(G) \to V(H)$$, such that $$(\phi(x),\phi(y)) \in E(H) \iff (x,y) \in E(G)$$, and the restriction $$\phi’\mid_A$$ is $$\phi$$. (i.e. $$\phi'(a) = \phi(a)$$ for all $$a \in A$$)

Does there exist a practical fast running algorithm for determining if such a $$\phi’$$ exists? If not, does there exist a simple heuristic algorithm which has a “decent chance” of answering in the affirmative.

I’m looking for an algorithm I can actually understand and code myself, rather than use a large complicated system like nauty.

## Complexity of Hamilton path in directed complete bipartite graphs

Finding a Hamiltonian path in a directed bipartite graph is NP-complete.

Problem 1 What is the complexity of the problem if we insist that the underlying graph of the digraph be complete bipartite? Is this known?

There is a variant of the problem we wish to consider

Problem 2 What is the complexity of the problem if the underlying graph is complete bipartite, and we specify the starting and ending vertex of the path?

## What is the probability that an expanding bipartite graph exists with the property, |V1|=|V2|?

I want to find a bound on the above problem, and show that a random graph has a positive probability of being an expanding bipartite with the property, |V1|=|V2|. I am not getting, where should I start.

Apologies for not writing my understanding, I am very much stuck.