# Questions tagged [bipartite-graphs]

The tag has no usage guidance.

29 questions
Filter by
Sorted by
Tagged with
79 views

### Alternative criterion for approximate maximum-weight perfect matching algorithms

I have asked this question in cs.stackeschange, and it was recommended to me that I asked it here. Is there any literature on approximate maximum-weight perfect matchings where the approximation ...
101 views

### Counting matchings on 3-regular bipartite graphs

What I call a graph here allows parallel edges. Is the following problem #P-hard: INPUT: a 3-regular bipartite graph $G$ OUTPUT: the number of matchings of $G$. It is known that counting matchings ...
130 views

### Does simplex algorithm run in polynomial on Bipartite Perfect matching polytope?

It is well known that simplex algorithm runs in exponential time in worst case. However are there situations (necessary and sufficient conditions) where simplex algorithm runs in polynomial time? In ...
132 views

### Finding a Hamiltonian cycle from perfect matching of a bipartite graph

A disjoint vertex cycle cover of G can be found by a perfect matching on the bipartite graph, H, constructed from the original graph, G, by forming two parts G (L) and its copy G(R) with original ...
339 views

### Generating a random connected bipartite graph

A (n, m, k)-bipartite graph is a bipartite graphs with: independent sets of size $\{n, m\}$ a total of $k \geq n+m-1$ edges We want an algorithm to generate a (n, m, k)-bipartite selected uniformly ...
91 views

### Algorithm for K-best NON perfect bipartite matchings

I was reading this great article: https://core.ac.uk/download/pdf/82129717.pdf It solves a generalization of the maximum sum assignment problem by finding the k best assignments and not only the best....
83 views

### Color shifting in a bipartite graph

Assume that we have a directed bipartite graph $G = \langle L\dot\cup R, E\rangle$. Where $E$ contains directed edges only from $L$ to $R$, that is, $E\subseteq L\times R$. Assume further that the ...
123 views

### Reducing resource allocation problem to bipartite matching

There are a set of bins, $B$ and a set of resources $R$. Each $b \in B$ is associated with a set function $Z_b(S) : 2^R \rightarrow \mathbb{R}^+$. The resource allocation problem is to find a ...
107 views

### Total flow using minimum number of edges on a bipartite network

If I have a set of sources $S$ with total capacity $C$ and a set of sinks $T$ with the same capacity $C$, but not necessarily the same cardinality, is there an efficient way to find the minimum number ...
349 views

### Is perfect matching for bipartite graph with no cycles unique?

Given a balanced bipartite graph that satisfies Hall's theorem (is non singular) then it shown that it has at least one perfect matching. My question is if the balanced bipartite graph is also ...
805 views

### Eigenvalues of adjacency matrix of a connected bipartite graph

Let $G=(V,E)$ is a connected d-regular bipartite graph with the same number of vertices on both sides of the bipartition. It's known that that the largest eigenvalue of its adjacency matrix would be d,...
254 views

### Efficient way to generate random planar cubic bipartite graphs

3-regular bipartite planar graphs appear in a variety of NP- / #P-complete problems. Suppose one wants to test the complexity of these problems via numerical experiments. Is there an efficient way to ...
113 views

### Is Permanent $+$-reducible?

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...
133 views

### What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?

We know counting perfect matching for bipartite graphs with vertex degree $2$ is in $P$ while counting perfect matching for graphs with vertex degree $3$ is in $\#P$. We also know there are degree $3$...
231 views

### 3-Hitting-Set - maximum flow algorithm [closed]

so i'm currently learning for an exam and got in an exercise the following question (a loose translation): Find an Algorithm that finds the smallest U' ⊆ U that is a solution the 3 HITTING SET ...
343 views

### What is a weakly-simplicial vertex?

While studying chordal bipartite graphs, I have come across weakly simplicial vertices. I have searched for some time to understand what a weakly simplicial vertex is but I haven't succeeded. A ...
159 views

### Maximum stable matching/allocation

I checked some papers on two-side stable allocation/matching (marriage, worker/company, doctor/hospital), but has not found any literature on the following problem. Can someone point out if I missed ...
263 views

### generate a graph with fixed min cut

Is there a constructive way to generate a graph with a fixed min cut equal to $k$? One approach is to generate a random graph and then try to make edges alterations (additions, deletions, swaps) to ...
Consider a bipartite graph $G=(X,Y)$, such that the degree of a left node $x \in X$ is $l$, and the degree of a right node $y \in Y$ is $r$. The number of edges is $|E|=|X|l=|Y|r$. Pick $w$ nodes in ...