Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
7 votes
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: ...
Noam Zeilberger's user avatar
6 votes
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 ...
Tim's user avatar
  • 627
5 votes
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 ...
Tassle's user avatar
  • 881
5 votes

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

PSPACE-completeness As suggested by Tim here, the problem can be shown to be PSPACE-hard by reduction from the Corridor Tiling Problem: Instance: a finite set of Wang tiles $\mathcal{T}=\{T_1,\ldots,...
Davide Zorzenon's user avatar
4 votes
Accepted

What is a weakly-simplicial vertex?

According to the 59th slide of the following pdf: https://grow2015.sciencesconf.org/file/174789 (A talk by D.Kratsch at GROW 2015) we have that A vertex in a graph is weakly simplicial if its ...
MonadBoy's user avatar
  • 156
4 votes
Accepted

Is Permanent $+$-reducible?

If you allow weighted edges and weighted perfect matchings (instead of just counts), then yes. I don't know a "nice" clean graph-theoretic description, but in principle one can be extracted ...
Joshua Grochow's user avatar
4 votes

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 ...
Christian Komusiewicz's user avatar
4 votes

Total flow using minimum number of edges on a bipartite network

Your problem is NP-hard. Consider a partition problem instance with input $a_1,\ldots,a_n$. We create a complete bipartite graph with $2$ source vertices each with capacity $\frac{1}{2} \sum_{i=1}^n ...
Chao Xu's user avatar
  • 4,479
4 votes
Accepted

Minimal clique edge cover vs minimalist (assignment-minimum) ones

Consider a graph on vertex set $V_1\cup V_2\cup V_3\cup V_4\cup \{a,b,c,d\}$ where $|V_1|=|V_2|=|V_3|=|V_4|=n$. The edge set $E$ is covered by $C=\{V_1\cup\{a,c\},V_2\cup\{a,d\},V_3\cup\{b,c\},V_4\cup\...
Wei Zhan's user avatar
  • 903
4 votes
Accepted

Connected dominating set in bipartite graphs

Yes, you can, by adapting the argument from this answer. Note that in a bipartite graph $G=(A, B, E)$, the set $B$ is a vertex cover. Lemma 1. Let $G$ be any $n$-vertex connected bipartite graph ...
Neal Young's user avatar
  • 10.8k
4 votes
Accepted

Complexity of maximum k-edge-colorable subgraph of a bipartite graph

A bipartite multigraph is $k$-edge colorable iff the maximum degree of any vertex is at most $k$. So we are asking for a subgraph $H=(V,F)$ of a given bipartite graph $G=(V,E)$ such that $\delta_H(v) \...
Chandra Chekuri's user avatar
4 votes
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$. ...
Neal Young's user avatar
  • 10.8k
3 votes
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 ...
smapers's user avatar
  • 849
3 votes

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-...
Chris Culter's user avatar
3 votes
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 ...
David Eppstein's user avatar
3 votes

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 ...
delete000's user avatar
  • 828
3 votes
Accepted

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

You can take any degree 3 bipartite graph $G$ and take its disjoint union $G'$ with a cycle $C$ of length 2m. The new graph $G'$ is bipartite, and has average degree $\frac{3n + 2m}{m+n} = 2 + \frac{n}...
Sasho Nikolov's user avatar
3 votes

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 ...
Christian Komusiewicz's user avatar
2 votes
Accepted

Maximum stable matching/allocation

Your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists). You can find the current best approximation algorithm for MAX SMTI in the following paper: Z. Kiraly, Linear ...
Hiroki Yanagisawa's user avatar
2 votes
Accepted

Online/approximate weighted and capacitated bipartite matching

I think there is no paper solving that exact problem, but "Online Vertex-Weighted Matching" by Aggarwal, Goel, Karande, and Mehta (2011) is very close. If I understood correctly, they solve your ...
usul's user avatar
  • 7,615
2 votes
Accepted

Color shifting in a bipartite graph

The precoloring extension problem is the following: Input: a number $k$ and a graph $G$ some of whose edges are labeled with labels in $\{1, 2, \ldots, k\}$. Decision: is it possible to color the ...
Mikhail Rudoy's user avatar
2 votes
Accepted

Finding a Hamiltonian cycle from perfect matching of a bipartite graph

If $G$ has a disjoint vertex cycle cover then I agree that $H$ must have a perfect matching, but I don't see the other direction (or I have misunderstood how you define $H$ exactly). I think the ...
M.Monet's user avatar
  • 1,429
2 votes

Constrained Bipartite Matching

This problem captures the maximum independent set problem, which is NP-hard, as follows. Suppose we wish to decide if a graph $H = (V_H, E_H)$ has an independent set of size $\ge k$. We construct $G = ...
Laakeri's user avatar
  • 1,786
2 votes
Accepted

Do such instances always admit a 3D matching?

How about the following counter-example? $m=2$, $n=4$. $A=\{a_1,a_2\}$, $B=\{b_1,b_2\}$, $C=\{c_1,c_2\}$. $T=\{(a_1,b_1,c_1), (a_1,b_2,c_2), (a_2,b_1,c_2), (a_2,b_2,c_1)\}$. With the partition $A\cup ...
Tassle's user avatar
  • 881
1 vote

Complexity and Algorithm for specific Vertex Separator Problem

I understand that the question is about the time bound, not about the correctness of the reduction. The claim does not sound obvious (although a bound of $\mathcal{O}(n^3n^2k)$ can be shown with a ...
Vinicius dos Santos's user avatar
1 vote

Bipartite graph projections, with threshold

My two cents: The worst case of building $G_\top$ is in $\Omega(n^2)$ time and space: assume $\bot$ contains a single node linked to all nodes in $\top$. Maybe you are not looking for a worst case ...
maxdan94's user avatar
  • 563
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 ...
Labo's user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
Neal Young's user avatar
  • 10.8k

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