13
votes
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 ...
- 5,772
9
votes
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.
...
- 4,449
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:
...
- 4,531
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 ...
- 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 ...
- 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,...
- 103
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 ...
- 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 ...
- 37.3k
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\...
- 828
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 ...
- 1,804
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 ...
- 4,449
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 ...
- 10.7k
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) \...
- 6,999
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$.
...
- 10.7k
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-...
- 151
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 ...
- 849
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 ...
- 51k
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 ...
- 818
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 ...
- 1,804
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}...
- 18.2k
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 ...
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 ...
- 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 ...
- 2,768
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 ...
- 1,429
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 ...
- 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 ...
- 1,868
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 ...
- 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 ...
- 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.7k
Only top scored, non community-wiki answers of a minimum length are eligible