# Tag Info

Accepted

### Complexity of counting matchings in a bipartite graph

The problem of counting such "imperfect" matchings in bipartite graphs is #P-complete. This has been proved by Les Valiant himself, on page 415 of the paper Leslie G. Valiant The Complexity of ...
Accepted

### Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard?

It's NP-complete by a reduction from cliques in graphs. Given an arbitrary graph $G$, construct a bipartite graph from its incidence matrix, by making one side $U$ of the bipartition correspond to the ...
Accepted

### Is "two or zero" matching in a bipartite graph NP complete?

The answer here seems to imply there is a more general result. For this particular case, here is a self contained way to reduce the problem to maximum weight perfect matching. Assume $k$ is even. ...
Accepted

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

Would you be satisfied with generating planar cubic bipartite maps (i.e., such graphs equipped with a planar embedding specified by a cyclic ordering on half-edges)? That problem was addressed in: ...
Accepted

### Complexity of "can we get a cycle by stacking directed bipartite graphs?"

Update: Davide showed that this problem is PSPACE-hard here, settling PSPACE-completeness. NP-hardness This is NP-hard by reduction from 3SAT. Let's consider a formula in $k$ variables. Below is the ...
Accepted

### Number of stable matchings

Yes. Thurber showed [1,Theorem 5] that for all $n\geq 1$, the maximum number of stable matchings is at least $\frac{(2.28)^n}{(1+\sqrt{3})^{1+\log_2 n}}$. If I'm not mistaken this is strictly greater ...

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

If the graph is acyclic, which implies that it is also bipartite, then the perfect matching is unique by the following algorithm: While the graph is not empty, pick a leaf vertex $u$ (which exists ...

Accepted

### Partition the edges of a bipartite graph into perfect $b$-matchings

Here's a counter-example for $k= 4$. Take $G = K_{2,2}$, specifically $G=(V, E)$ where $V=\{1,2,3,4\}$ and $E=\{(1,3), (1, 4), (2,3), (2,4)\}$. Define $b^1$ by $b^1_1 = b^1_3 = 1$ and $b^1_2=b^1_4=0$. ...
Accepted

### Is there a regular bipartite graph where the minimum cuts are trivial?

An $r$-regular expander should do it. The following is a simple observation that I first saw in Li (arXiv:2106.05513): if an $r$-regular graph has conductance $\phi$, then the smaller side $S$ of a ...

### Covering a binary relation as a union of rectangles

...aha, found it! This is the bipartite dimension problem, and yes it is NP-hard without further assumptions. Previously asked here: https://cs.stackexchange.com/questions/49266/finding-a-minimal-...
Accepted

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

This fact can be found in Godsil, C. D. (1985), "Inverses of trees", Combinatorica 5 (1): 33–39, doi:10.1007/BF02579440 (without proof, near the bottom of the first page): "noting that a tree with a ...

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

In case anyone else is looking for a practical answer: the program plantri by Brinkmann and McKay can generate small (up to 64 vertices as-is, up to 255 with some hacking) planar bipartite cubic ...

### generate a graph with fixed min cut

In his 1962 paper "The Maximum Connectivity of a Graph", Harary describes a way to construct for integers $p$ and $q$ with $q\ge p-1$ a way to construct a graph with $p$ vertices and $q$ edges that ...
Accepted

1 vote

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

After some thinking, I found an answer. If one has a better one I'll accept it. From a cost matrix of shape $n\times m$ with $n<m$, it is easy to add nodes that will not change anything by giving ...
1 vote

### Reducing resource allocation problem to bipartite matching

Yes, there certainly is. There is a trivial solution. First, solve the resource allocation problem (which can be done in exponential time by enumerating all candidate solutions). Then, use the ...

Only top scored, non community-wiki answers of a minimum length are eligible