Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [bipartite-graphs]

The tag has no usage guidance.

9
votes
2answers
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 ...
9
votes
1answer
258 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 ...
7
votes
1answer
453 views

Is “two or zero” matching in a bipartite graph NP complete?

I have this problem, which I haven't seen before in the literature: given a bipartite graph and a natural number $k$, can we select at least $k$ of the edges such that each left-hand vertex is ...
5
votes
2answers
228 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 ...
5
votes
1answer
290 views

Sparser Bipartite graphs?

Maximal Planar Bipartite graphs are sparser than maximal planar graphs. For which other classes of graphs are maximal Bipartite members sparser than arbitrary maximal members. Let $\mathcal{C}$ be a ...
5
votes
1answer
762 views

Assignment problem with multiple workers for each job

I am wondering if there are any results on the following version of the assignment problem. We are given a set of jobs $J$ and a set of workers $W$, and for each job $j$ and worker $w$ we are given ...
4
votes
1answer
248 views

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

Given: A bipartite graph G=(U,V,E) Integers n and k. Decision Problem: Is there a subset of U of size k that has at most n neighbours? I am trying to figure out whether this problem is NP-hard (...
4
votes
1answer
476 views

Constrained version of vertex cover in a bipartite graph

Let $G(V_1, V_2, E)$ be a bipartite graph such that degree of all the vertices in $V_1$ is bounded by some constant (say) $d$. Now, for given two positive integer $l$ and $k$, we wish to decide if ...
3
votes
0answers
78 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 ...
3
votes
0answers
158 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,...
3
votes
0answers
111 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 ...
2
votes
1answer
145 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 ...
2
votes
1answer
224 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 ...
2
votes
0answers
54 views

Degree distribution of certain subgraphs of a biregular graph

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 ...
1
vote
2answers
198 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 ...
1
vote
1answer
106 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 ...
1
vote
1answer
269 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 ...
1
vote
1answer
70 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 ...
1
vote
1answer
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....
1
vote
0answers
104 views

algorithms for a large submatrix / general factor / quasi-biclique problem?

Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that ...
1
vote
0answers
89 views

Algorithm for maximum bipartite matching with arriving edges?

Given a bipartite graph with fixed nodes and incrementally arriving edges, is there any efficient algorithm to compute and update the maximum matching?
0
votes
1answer
95 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$...
0
votes
1answer
187 views

Online/approximate weighted and capacitated bipartite matching

I wish to take a look at online/approximate weighted and capacitated bipartite matching problem. Consider $G=\{L\cup R, E\}$, $|L|=n_1$, $|R|=n_2$, $|E|=m$ and $E\subseteq L\times R$. For each $r_i\...
0
votes
0answers
2 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 ...
-1
votes
1answer
91 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 ...
-2
votes
1answer
131 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 ...