# Questions tagged [bipartite-graphs]

The tag has no usage guidance.

49 questions
Filter by
Sorted by
Tagged with
398 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 ...
• 9,458
3k 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,547
747 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 ...
215 views

### Counting matchings on 3-regular bipartite graphs

What I call a graph here allows parallel edges. Is the following problem #P-hard: INPUT: a 3-regular bipartite graph $G$ OUTPUT: the number of matchings of $G$. It is known that counting matchings ...
• 1,429
296 views

• 177
145 views

• 151
282 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 ...
107 views

### Constrained Bipartite Matching

Let $G = (X,Y,E)$ be a bipartite graph. For some $A \subseteq X$ we say that $A$ can be perfectly matched if there is a matching $M \subseteq E$ such that all vertices in $A$ are matched; that is, for ...
• 412
152 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 ...
• 33
175 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 ...
• 119
65 views

• 113
1 vote
147 views

• 119
134 views

### Complexity and Algorithm for specific Vertex Separator Problem

Given a graph $\Gamma=(V,E)$ with vertex set $V$ and edge set $E$ a $\textit{three partition}$ is decomposition of $V$ into a triple $(V_1, S, V_2)$ such that vertices of $V_1$ are only incident to ...
38 views

### Bipartite Matching with a Partition Constraint over the Vertices

Let $G = (X,Y,E)$ be a bipartite graph and let $X_1,\ldots,X_r$ be a partition of $X$. For some $i \in \{1,\ldots, r\}$ and $E' \subseteq E$ we say that constraint $X_i$ is covered by some $E'$ if ...
• 412
47 views

### On a modular inverse graph construction

Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ ...
• 13k
137 views

### Error in TAOCP 4a on the bipartite graph constructed from a hypergraph

The first sentence on page 33 of Donald Knuth's The Art of Computer Programming (TAOCP) Vol. 4a reads: Furthermore, a hypergraph is equivalent to a bipartite graph with vertex set $V \cup E$ and ...
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 ...