Questions tagged [bipartite-graph]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
28 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 ...
5
votes
1answer
58 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 \...
0
votes
0answers
11 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 ...
0
votes
0answers
25 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 ...
1
vote
1answer
50 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
2answers
98 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
1answer
53 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 ...
2
votes
0answers
66 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
1answer
59 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
1answer
81 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
2answers
81 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 ...
0
votes
1answer
45 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 ...
5
votes
1answer
138 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 ...
2
votes
1answer
50 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 $\...
0
votes
1answer
122 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 ...
1
vote
1answer
19 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 ...
-1
votes
1answer
41 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
1answer
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
1answer
35 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
1answer
286 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'$?
3
votes
1answer
146 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$. ...
2
votes
2answers
337 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
1answer
373 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 ...
2
votes
1answer
47 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 ...
0
votes
0answers
115 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
0answers
32 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 ...
4
votes
2answers
260 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
1answer
71 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, ...
3
votes
2answers
197 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 ...
1
vote
1answer
393 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 ...