Tag Info

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: ...
• 4,521
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 ...
• 627
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 ...
• 881

• 4,479
Accepted

• 6,999
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$. ...
• 10.8k
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 ...
• 849

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-...
• 151
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 ...
• 828
Accepted

• 1,786
Accepted

• 129
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 ...
• 12.1k
1 vote

Maximum weight "fair" matching

I believe "maximum weight fair bipartite matching" as you've defined it is NP-hard. Even more, determining the existence of a fair bipartite matching is NP-hard. Before I give a proof sketch, for ...
• 10.8k

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