# Questions tagged [bipartite-graph]

The tag has no usage guidance.

39 questions
Filter by
Sorted by
Tagged with
1 vote
22 views

### Code to list all maximal bicliques of a bipartite graph

We are looking for a code to list all maximal bicliques in bipartite graphs efficiently, as we want to run it on (large and sparse) graphs, with up to roughly a million nodes and edges in no more that ...
48 views

### Is it possible to have a 2 by 2 rigid framework without having a corresponding connected bipartite graph?

According to the theorem(see reference) on the rigidity of frameworks: A rectangular framework is rigid if and only if its associated bipartite graph is connected. Now consider the case for a 2-by-2 ...
166 views

### Algorithm to find a set of nodes with a smaller set of neighbours in a bipartite graph

Given a bipartite graph, find a set of nodes on one side that has greater cardinality than the set of its neighbours on the other side. This is a conceptually simple problem, but I suspect it is ...
51 views

### For a regular bipartite graph with vertices $X\cup Y$, prove that $|S|\leq|n(S)|$ $\forall S\subseteq X$

As the title states, we are given a bipartite undirected graph $G=(X\cup Y,E)$ such that every vertex $v\in V$ satisfies $d(v)=k$ for a constant $k$. The general goal of the proof is to show that ...
54 views

### Searching for the largest bipartite subgraph

OpenAI's Chat-GPT told me: There is no known exact algorithm for finding the largest bipartite subgraph in a graph in polynomial time. This problem is generally believed to be NP-hard, which means ...
305 views

### Algorithm for maximum non-crossing edge set in bipartite graph with a fixed permutation

I'm trying to identify an algorithm to solve this computational problem Input: Bipartite graph (V, W, E), with E ⊆ V×W A fixed ...
22 views

### How can I find the largest bipartite graph?

A bipartite graph corresponds to a rectangle of ones in the adjacency matrix of this graph. Having a sparse graph, I would like to find the largest approximated bipartite graph. approximated means ...
23 views

### Unique perfect matching in unweighted bipartite graph

Say I have a bipartite graph G with vertex set A and B when |A|=|B|=n and edge set E. Then how do I determine whether the graph has unique matching efficiently. I am not sure but the permanent of ...
1 vote
44 views

### Split Bipartite Graph

I have a bipartite graph $G=(U=\{U_1, U_2,\cdots\}, V=\{V_1, V_2,\cdots\} , E)$ such that edges don't "skip" the $V$ vertices. Meaning, if edge $(U_i, V_j)$ doesn't exist, neither will edges ...
94 views

### Name and complexity of this problem on bipartite graphs

Let $G=(U, V, E)$ be a biparite graph, with $U$ and $V$ being the two sets of nodes. I am trying to find the smallest set of nodes $\hat{V} \subseteq V$ such that, for every node $u \in U$, $\hat{V}_u$...
1 vote
57 views

1 vote
62 views

### a lower bound for the maximum fraction of matchings not containing an edge

I am trying to prove the following statement (from book, page 317): Let $G(A,B,E)$ be a bipartite graph, where $A$ and $B$ are the two disjoint sets of vertices s.t. $|A|=|B|=n$. Let the number of ...
1 vote
369 views

### Bipartite Graph to solve the wolf river crossing problem

I have just started studying about bipartite graphs and there is an example that bipartite graph can be use to solve the wolf, cabbage, and the sheep river crossing problem, as a kid i had fun solving ...
1 vote
125 views

### looking for counterexample for my algorithm for maximum independent set in Bipartite Graph

We wish to find the maximum independent set in a bipartite graph. My intuition led me to the following algorithm. (Assume that the bipartite graph is connected and has at least 3 vertices, if not run ...
155 views

### Assignment Problem with Minimum and Maximum constraints [duplicate]

I have the following problem: In a school, there are n students and m clubs, with n > m. Each student needs to be assigned a club. The students have preferences, (say top 3 or top 5) of the clubs ...
1 vote
77 views

### How to find a cut in a graph with additional constraints?

I have a complete undirected graph $G=(V,E)$ with positive non-null rational weights $c:E \to \mathbb{Q}^+_{*}$ on the edges, such that $c(v,v) = 0$ for all $v$, and a subset $C \subset V$. I would ...
1 vote
211 views

### Maximum one-to-many matching

Let $G = (X+Y,E)$ be a bipartite graph and $k\geq 1$ an integer. A maximum $k$-matching is a subset of $E$ in which each vertex of $X$ is adjacent to at most $k$ edges and each vertex of $Y$ is ...
1 vote
157 views

### Bipartite graphs with min weights

I have a full bipartite graph with node sets $A=\{a_1,a_2,\ldots,a_n\}$ and $B=\{b_1,b_2,\ldots,b_n\}$. Each node has a weight, $v_i$ for $a_i$ and $w_i$ for $b_i$. Each node $a_i$ is connected to ...
61 views

### Bipartite Graph in a Digraph

How do you find a sub-digraph in a digraph such that the in degree and out degree of each vertex is 1. My professor told in the class that an algorithm can be build for it using bipartite matching but ...
189 views

### Saturated sets in bipartite graph

Let $G=(X\cup Y, E)$ be an unweighted bipartite graph. We are given that for every $W\subseteq X$ it holds that $|W|\leq |N(W)|$, where $N(W)$ is the neighborhod of $W$ in $Y$ (aka Hall's marriage ...
59 views

819 views

### Bipartite graph minimal amount of vertices required

I have a bipartite graph made of two sets (SET 1 and SET 2) and I want to determine how many vertices from the ...
1 vote
842 views

### Path finding through bipartite graph

Is there a path finding algorithm that exploits a directed bipartite graphs' structure? I found this: Shortest-Path for Weighted Directed Bipartite Graphs but it didn't seem like the OP needed a ...
64 views

### Another vertex cover question?

I'm not sure this is equivalent to bipartite vertex cover question. The question is: Given a BIPARTITE graph, what is the minimum number of vertex from the right side whose edges cover all vertex ...
160 views

### What is the approximation for odd cycle transversal?

What is the best approximation for odd cycle transversal? (on general graphs) Sorry if this is easily found everything I found about odd cycles is about paramaterized complexity and kernels
1 vote
48 views

### bipartite d regular expender explicit construction

I am looking for an explicit (and simple) construction of a d regular bi bipartite graph which is an expander. I searched the web and didn't find any sufficient answer. The only explicit graph I did ...
368 views

### Does real linear programming produce bipartite perfect matching using maxflow reduction?

Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram: We can formulate max flow as an linear programming problem with integer variables in ...
1 vote
130 views

### Algorithm to assign producers to consumers with respect to connections

I am trying to analyze supply chains in a game and have come across this problem: First, an informal description: I have producers and consumers. Each producer produces a certain amount of goods, ...