Questions tagged [bipartite-graph]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
34 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 ...
user avatar
  • 53
0 votes
0 answers
20 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 ...
user avatar
0 votes
0 answers
13 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 ...
user avatar
  • 11
1 vote
0 answers
34 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 ...
user avatar
  • 143
5 votes
2 answers
86 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$...
user avatar
1 vote
1 answer
31 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 $...
user avatar
0 votes
0 answers
31 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 ...
user avatar
  • 1
5 votes
1 answer
64 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 \...
user avatar
  • 75
0 votes
0 answers
12 views

Find a matching of a bipartite graph that uses all vertices in the left set

I have a bipartite graph already divided into a left and right set, and I would like to find a matching that uses all of the vertices in the left set. To phrase this problem less abstractly, I have a ...
user avatar
0 votes
0 answers
34 views

Algorithm for bipartite graph matching decision problem

Suppose I have a list of sets $$ L=\{A_1,A_2,\ldots ,A_n\} $$ And want and algorithm that solves the following decision problem Is it possible to select one element from each set such that no two ...
user avatar
  • 519
1 vote
1 answer
54 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 ...
user avatar
1 vote
2 answers
171 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 ...
user avatar
  • 341
1 vote
1 answer
67 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 ...
user avatar
  • 113
2 votes
0 answers
96 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 ...
user avatar
  • 275
1 vote
1 answer
64 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 ...
user avatar
1 vote
1 answer
126 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 ...
user avatar
1 vote
2 answers
93 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 ...
user avatar
0 votes
1 answer
51 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 ...
user avatar
  • 49
5 votes
1 answer
152 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 ...
user avatar
  • 199
2 votes
1 answer
55 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 $\...
user avatar
0 votes
1 answer
135 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 ...
user avatar
1 vote
1 answer
22 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 ...
user avatar
  • 168
-1 votes
1 answer
46 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 ...
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$ ...
user avatar
-1 votes
1 answer
36 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 ...
user avatar
4 votes
1 answer
311 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'$?
user avatar
3 votes
1 answer
164 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$. ...
user avatar
2 votes
2 answers
467 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 ...
user avatar
  • 23
1 vote
1 answer
491 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 ...
user avatar
2 votes
1 answer
51 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 ...
user avatar
0 votes
0 answers
133 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
user avatar
  • 83
1 vote
0 answers
37 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 ...
user avatar
  • 209
4 votes
2 answers
298 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 ...
user avatar
  • 2,824
1 vote
1 answer
85 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, ...
user avatar
  • 113
3 votes
2 answers
214 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 ...
user avatar
1 vote
1 answer
417 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 ...
user avatar