Questions tagged [bipartite-graph]
The bipartite-graph tag has no usage guidance.
39
questions
1
vote
0
answers
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 ...
- 11
2
votes
1
answer
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 ...
- 143
4
votes
1
answer
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 ...
- 297
2
votes
1
answer
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 ...
- 315
0
votes
2
answers
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 ...
- 59
3
votes
1
answer
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 ...
- 53
0
votes
0
answers
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 ...
- 59
0
votes
0
answers
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 ...
- 11
1
vote
0
answers
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 ...
- 143
5
votes
2
answers
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
1
answer
57
views
Optimal prune of a mutually-exclusive bipartite graph
I start with a complete edge-weighted unbalanced bipartite graph.
For a known, fixed $n$ on the order of 1000:
$$0 \lt n, n \in I$$
Left and right cardinalities might not be equal; for sides $U$ and $...
- 237
0
votes
0
answers
37
views
Difficulty in finding a counter example for a polynomial reduction
I am doing some exercises on proving NP Complete problems and the first problem was directed bipartite graphs with a Hamiltonian cycle and the second one was undirected bipartite graphs with a ...
- 1
5
votes
1
answer
82
views
The maximum matching of a bipartite graph $(S, T)$ is $|X|+\min\limits_{A \subseteq X} (\min\{0, |N_G(A)|-|A|\}$, where $X \in \{S, T\}$?
Here is the full version of the problem I'm dealing with.
Let $G=(S,T;E)$ be a bipartite graph and let $X$ be one of the two classes of its bipartition (i.e., $X \in \{S,T\}$). For a subset $C \...
- 75
1
vote
1
answer
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 ...
- 2,933
1
vote
2
answers
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 ...
- 339
1
vote
1
answer
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 ...
- 113
2
votes
0
answers
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 ...
- 285
1
vote
1
answer
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
1
answer
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 ...
- 5,790
1
vote
2
answers
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 ...
- 942
0
votes
1
answer
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 ...
- 49
5
votes
1
answer
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 ...
- 229
2
votes
1
answer
59
views
Does this problem map to the Set Packing problem?
Let $G(m,n)$ be A bipartite graph $G$ with paritions $m$ and $n$ with the property that partition $\mathit n$ has two types of nodes (type1 or type2).
Given $G(m,n)$ and $k \in \mathbb Z+$:
Does $\...
- 23
0
votes
1
answer
192
views
Algorithm to split bipartite graph into subgraphs
I'm looking for an algorithm to split a bipartite graph into subgraphs with a specific constraint. I'm not sure if any existing algorithms solve my problem or not.
I have an undirected bipartite ...
- 103
1
vote
1
answer
24
views
Equivalence between MIN UNCUT and MIN-CSP_XOR
In this paper
Agarwal, Amit, et al. "O (√ log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems." Proceedings of the thirty-seventh annual ACM symposium on ...
- 168
-1
votes
1
answer
57
views
Find bipartial subgraph such that number of edges is maximum and sum of edge lengths is maximum
Let there be graph $G = (V, E)$. $G$ has neither loops nor parallel arcs.
$V = A \cup B, \, A \neq \emptyset, \, B \neq \emptyset, A \cap B = \emptyset$
For simplicity's sake, let's consider $G$ is ...
-1
votes
1
answer
30
views
Find bipartial subgraph such that mean square deviation of edge lengths is minimum
Let there be graph $G = (V, \, E)$. $G$ has neither loops nor parallel arcs.
$V = A \cup B, \, A \neq \emptyset, \, B \neq \emptyset, A \cap B = \emptyset$
For simplicity's sake, let's consider $G$ ...
-1
votes
1
answer
38
views
Find bipartial subgraph such that sum of edge lengths is maximum
Let there be graph $G = (V, E)$. $G$ has neither loops nor parallel arcs.
$V = A \cup B, \, A \neq \emptyset, \, B \neq \emptyset, A \cap B = \emptyset$
For simplicity's sake, let's consider $G$ is ...
4
votes
1
answer
346
views
Maximum matching in a bipartite graph
Given a bipartite graph $G=(V_1 \cup V_2, E)$ and a set $V' \in (V_1 \cup V_2)$. What is the complexity of finding a maximum matching in $G$ that uses only $x$ vertices from $V'$?
- 385
3
votes
1
answer
181
views
Assignment Problem -- finding the $k$ agents with the best assignment
I have a question that I have been thinking about. Suppose we have $n$ agents, $m$ tasks, a cost matrix with $M_{ij}$ being the cost of agent $i$ performing task $j$, and are given a value $k \leq n$. ...
- 61
2
votes
2
answers
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 ...
- 23
1
vote
1
answer
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 ...
- 13
2
votes
1
answer
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 ...
- 23
0
votes
0
answers
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
- 83
1
vote
0
answers
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 ...
- 209
4
votes
2
answers
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 ...
- 2,861
1
vote
1
answer
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, ...
- 113
3
votes
2
answers
261
views
Is every X3SAT instance with no cycles satisfiable?
Exactly 1 in 3 SAT (X3SAT) is a variation of the Boolean Satisfiability problem. Given a set of clauses, where each clause has three literals, is there an assignment such that in each clause exactly ...
- 341
1
vote
1
answer
491
views
Partitioning vertices in a bipartite graph according to minimum vertex covers
How to solve this problem?
A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover with ...
- 394