# Questions tagged [bipartite-graphs]

The tag has no usage guidance.

30 questions
Filter by
Sorted by
Tagged with
61 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 ...
83 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 ...
84 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 ...
60 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 ...
28 views

### Alternating Delivery Problem

What is known about the complexity of the following problem: Suppose we have a complete bipartite graph $G(V,E)$ with disjoint sets $C$ and $T$. The candidate vertices, and the target vertices ...
104 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 ...
80 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....
72 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 ...
1k 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 bipartite ...
98 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 ...
264 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 ...
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 ...
216 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 ...
254 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,...
234 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 ...
112 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 ...
100 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$...
169 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 ...
294 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 ...
147 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 ...
232 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 ...