Questions tagged [bipartite-graph]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
16 views

Kernelization For Odd Cycle Transversal Problem on Perfect Graphs

This problem appears as exercise 2.33 in https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (page 48). A perfect graph $G$ is bipartite if and only if it contains no triangle graphs. ...
Yavuz Bozkurt's user avatar
2 votes
1 answer
39 views

Finding a Maximum Cut With Force Labeled Vertices for Planar Graphs

The maximum cut problem is a combinatorial optimization problem that seeks to partition the vertices of a graph into two sets, $S$ and $T$, in a way that maximizes the number of edges that cross ...
Daniel García's user avatar
1 vote
1 answer
63 views

Scheduling classes with lower and upper bounds on students and classes

I am struggling to solve the following excercise: Design an assignment of a group of n students to m classes. Student i should take a minimum of $l_i$, and a maximum of $u_i$ within a set C1 of ...
FarsoFracico's user avatar
1 vote
1 answer
95 views

Expected maximum matching size in a random bipartite graphs

What is the expected maximum matching size of a bipartite graph $(A\cup B, V)$ where $\lvert A\rvert = n$ and $\lvert B\rvert = n$ and the probability of a edge existing between $A$ and $B$ is a fixed ...
Anonymous's user avatar
2 votes
1 answer
70 views

Dinitz’ algorithm in simple unit-capacity networks

I am studying for an algorithm design course, and can't understand this demonstration about how Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time. This is what is written on the slides ...
Placido Pellegriti's user avatar
1 vote
0 answers
26 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 ...
Alt-Tab's user avatar
  • 11
2 votes
1 answer
51 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 ...
Aniruddha's user avatar
  • 143
4 votes
1 answer
203 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 ...
Ray Butterworth's user avatar
2 votes
1 answer
55 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 ...
Aishgadol's user avatar
  • 355
0 votes
2 answers
139 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 ...
nuemlouno's user avatar
3 votes
1 answer
471 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 ...
Jordan's user avatar
  • 53
0 votes
0 answers
26 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 ...
nuemlouno's user avatar
0 votes
0 answers
28 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 ...
Anshul's user avatar
  • 11
1 vote
0 answers
46 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 ...
Jon Nir's user avatar
  • 143
5 votes
2 answers
97 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$...
Luigi Procopio's user avatar
1 vote
1 answer
67 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 $...
Reinderien's user avatar
0 votes
0 answers
43 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 ...
sari98's user avatar
  • 1
5 votes
1 answer
83 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 \...
0410's user avatar
  • 75
1 vote
1 answer
64 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 ...
advocateofnone's user avatar
1 vote
2 answers
488 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 ...
kiv's user avatar
  • 339
1 vote
1 answer
161 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 ...
Anvit's user avatar
  • 113
2 votes
0 answers
207 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 ...
devam_04's user avatar
  • 285
1 vote
1 answer
95 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 ...
Matheus Diógenes Andrade's user avatar
1 vote
1 answer
233 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 ...
Erel Segal-Halevi's user avatar
1 vote
2 answers
183 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 ...
Zirui Wang's user avatar
0 votes
1 answer
64 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 ...
Bajru's user avatar
  • 49
5 votes
1 answer
200 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 ...
AvidLearner's user avatar
2 votes
1 answer
67 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 $\...
PlasticCasio's user avatar
0 votes
1 answer
231 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 ...
Neil Brown's user avatar
1 vote
1 answer
26 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 ...
cangrejo's user avatar
  • 168
-1 votes
1 answer
59 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 ...
memoryallocator's user avatar
-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$ ...
memoryallocator's user avatar
-1 votes
1 answer
39 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 ...
memoryallocator's user avatar
4 votes
1 answer
382 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'$?
Farah Mind's user avatar
3 votes
1 answer
189 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$. ...
user89692's user avatar
2 votes
2 answers
1k 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 ...
Neirpyc's user avatar
  • 23
1 vote
1 answer
1k 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 ...
Bill Quesy's user avatar
2 votes
1 answer
70 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 ...
Junrui Tao's user avatar
0 votes
0 answers
169 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
Hao S's user avatar
  • 83
1 vote
0 answers
55 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 ...
misha312's user avatar
  • 209
4 votes
2 answers
416 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 ...
Turbo's user avatar
  • 2,891
1 vote
1 answer
161 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, ...
jalgames's user avatar
  • 113
3 votes
2 answers
274 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 ...
Russell Easterly's user avatar
1 vote
1 answer
544 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 ...
Manoharsinh Rana's user avatar