Questions tagged [bipartite-graphs]
The bipartite-graphs tag has no usage guidance.
50
questions
2
votes
0
answers
138
views
Counterexample for the 1-optimal matching algorithm in Gabow's and Tarjan's paper on scaling algorithms for networks
Context
I am reading Faster scaling algorithms for network problems by Gabow and Tarjan where I am researching part 2: "Matching and extensions". However, I am a bit confused with the ...
- 21
2
votes
2
answers
108
views
Weighted bipartite matching with no-cycle constraint
Given a weighted bipartite graph, I need to find a maximum-weight matching with the following additional constraint: the residual graph of the chosen matching is not allowed to contain any cycles. By ...
- 233
1
vote
0
answers
89
views
Development details of the Hungarian algorithm for Maximum Perfect Bipartite Matching
There are two realization forms of Hungarian algorithm. One is the original dynamic matrix, and the other is via equality subgraph. I just checked the original paper of Hungarian method by Kuhn, which ...
2
votes
1
answer
112
views
Constrained Bipartite Matching
Let $G = (X,Y,E)$ be a bipartite graph. For some $A \subseteq X$ we say that $A$ can be perfectly matched if there is a matching $M \subseteq E$ such that all vertices in $A$ are matched; that is, for ...
- 412
0
votes
0
answers
45
views
Bipartite Matching with a Partition Constraint over the Vertices
Let $G = (X,Y,E)$ be a bipartite graph and let $X_1,\ldots,X_r$ be a partition of $X$.
For some $i \in \{1,\ldots, r\}$ and $E' \subseteq E$ we say that constraint $X_i$ is covered by some $E'$ if ...
- 412
0
votes
0
answers
52
views
On a modular inverse graph construction
Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ ...
- 13.1k
0
votes
0
answers
140
views
Error in TAOCP 4a on the bipartite graph constructed from a hypergraph
The first sentence on page 33 of Donald Knuth's The Art of Computer Programming (TAOCP) Vol. 4a reads:
Furthermore, a hypergraph is equivalent to a bipartite graph with vertex set $V \cup E$ and ...
4
votes
1
answer
77
views
Complexity of maximum k-edge-colorable subgraph of a bipartite graph
Can the maximum $k$-edge-colorable subgraph of a bipartite graph be found in polynomial time? Equivalently, can the maximum $k$-colorable subgraph of the line graph of a bipartite graph be found in ...
- 7,590
3
votes
0
answers
145
views
On perm+1 and det+1
Given a balanced bipartite graph G and a planar graph H. We do not know the number of perfect matchings in G and we do not know the number of spanning trees in H. But assume they are at least 3 both.
...
- 13.1k
0
votes
1
answer
138
views
Complexity and Algorithm for specific Vertex Separator Problem
Given a graph $\Gamma=(V,E)$ with vertex set $V$ and edge set $E$ a $\textit{three partition}$ is decomposition of $V$ into a triple $(V_1, S, V_2)$ such that vertices of $V_1$ are only incident to ...
2
votes
0
answers
70
views
Is there a term for expander-like graphs that expand only large subsets?
I would like to find a bipartite graph $G(L, R)$ with the following properties/constraints:
For every subset $S \subseteq R$ with $\bf{|S| \geq \alpha |R|}$, its neighborhood $\Gamma(S)$ satisfies $|\...
- 21
3
votes
1
answer
173
views
Connected dominating set in bipartite graphs
Let $G$ a bipartite graph with two disjoint set of vertices $\mathbf{A}$ and $\mathbf{B}$.
Denote $n_a:=|\mathbf{A}|$, $n_b:=|\mathbf{B}|$. Suppose the following conditions hold:
$\Theta(1)<n_b<...
- 177
2
votes
0
answers
60
views
Is Finding an *Unbalanced* Biclique in Bipartite Graphs Hard?
In the balanced biclique in bipartite graphs (MBB) problem we are given a bipartite graph $G = (L,R,E), |L| = |R| = n$ and the goal is to find an induced subgraph of $G$, $G' = (L',R',E')$, with as ...
- 412
1
vote
1
answer
337
views
Number of stable matchings
In the stable marriage problem, is it possible to find an instance with $2^{n -1}$ stable matchings when $n$ is a power of 2 (or just even)? If yes, how? I know how to build an instance in which $2^{n/...
- 113
5
votes
2
answers
296
views
Complexity of "can we get a cycle by stacking directed bipartite graphs?"
Preliminaries
We consider directed bipartite graphs of the form $G = (V,V',E)$, in which the nodes are partitioned into $V = \{1,\ldots,n\}$ and $V'=\{1',\ldots,n'\}$, with $|V|=|V'|=n$, and $E\...
- 103
1
vote
1
answer
149
views
Partition the edges of a bipartite graph into perfect $b$-matchings
Any $r$-regular bipartite graph can be partitioned into $r$ disjoint perfect matchings.
I want to know whether a version of this extends to perfect $b$-matchings.
Suppose we have a bipartite graph $G =...
- 649
1
vote
1
answer
134
views
Is there a regular bipartite graph where the minimum cuts are trivial?
My question is: Given integers $r$ and $k$, is there an $r$-regular bipartite graph $G = L \cup R$ with $|L| = |R| = k$, which is $r$-edge connected, and such that every minimum cut is trivial?
We can ...
- 649
0
votes
1
answer
68
views
Do such instances always admit a 3D matching?
I want to know whether the following kinds of special instances of the 3D Matching problem are ``yes" instances, i.e., admit a 3D matching.
We are given 3 sets $A,B,C$ containing $m$ elements ...
- 15
2
votes
1
answer
78
views
Covering a binary relation as a union of rectangles
Given finite sets $X$ and $Y$ and a subset $R\subset X\times Y$, I want to express $R$ as a union $R=\bigcup_{i=1}^n X_i\times Y_i$ with $n$ as small as possible. Here, each $X_i\subset X$ and $Y_i\...
- 151
1
vote
1
answer
82
views
Bipartite graph projections, with threshold
Let $G=(\top,\bot,E)$ be a bipartite graph: $E\subseteq \top\times\bot$.
The projections $G_\bot = (\bot,E_\bot)$ and $G_\top = (\top,E_\top)$ of $G$ are defined as follows: two vertices are linked ...
- 693
3
votes
1
answer
148
views
Minimal clique edge cover vs minimalist (assignment-minimum) ones
Given a graph $G=(V,E)$, a clique edge cover is a collection $C$ of subsets of $V$ such that each element $c$ of $C$ is a clique ($c \times c \subseteq E$) and $G$ is the union of these cliques ($E = \...
- 693
2
votes
0
answers
96
views
Alternative criterion for approximate maximum-weight perfect matching algorithms
I have asked this question in cs.stackeschange, and it was recommended to me that I asked it here.
Is there any literature on approximate maximum-weight perfect matchings where the approximation ...
- 29
6
votes
0
answers
218
views
Counting matchings on 3-regular bipartite graphs
What I call a graph here allows parallel edges.
Is the following problem #P-hard:
INPUT: a 3-regular bipartite graph $G$
OUTPUT: the number of matchings of $G$.
It is known that counting matchings ...
- 1,431
1
vote
0
answers
367
views
Does simplex algorithm run in polynomial on Bipartite Perfect matching polytope?
It is well known that simplex algorithm runs in exponential time in worst case.
However are there situations (necessary and sufficient conditions) where simplex algorithm runs in polynomial time?
In ...
- 13.1k
1
vote
1
answer
1k
views
Finding a Hamiltonian cycle from perfect matching of a bipartite graph
A disjoint vertex cycle cover of G can be found by a perfect matching on the bipartite graph, H, constructed from the original graph, G, by forming two parts G (L) and its copy G(R) with original ...
4
votes
0
answers
1k
views
Generating a random connected bipartite graph
A (n, m, k)-bipartite graph is a bipartite graphs with:
independent sets of size $\{n, m\}$
a total of $k \geq n+m-1$ edges
We want an algorithm to generate a (n, m, k)-bipartite selected uniformly ...
- 141
1
vote
1
answer
104
views
Algorithm for K-best NON perfect bipartite matchings
I was reading this great article: https://core.ac.uk/download/pdf/82129717.pdf
It solves a generalization of the maximum sum assignment problem by finding the k best assignments and not only the best....
- 129
1
vote
1
answer
152
views
Color shifting in a bipartite graph
Assume that we have a directed bipartite graph $G = \langle L\dot\cup R, E\rangle $. Where $E$ contains directed edges only from $L$ to $R$, that is, $E\subseteq L\times R$. Assume further that the ...
- 23
-1
votes
1
answer
194
views
Reducing resource allocation problem to bipartite matching
There are a set of bins, $B$ and a set of resources $R$. Each $b \in B$ is associated with a set function $Z_b(S) : 2^R \rightarrow \mathbb{R}^+$. The resource allocation problem is to find a ...
- 111
1
vote
1
answer
231
views
Total flow using minimum number of edges on a bipartite network
If I have a set of sources $S$ with total capacity $C$ and a set of sinks $T$ with the same capacity $C$, but not necessarily the same cardinality, is there an efficient way to find the minimum number ...
- 19
1
vote
2
answers
961
views
Is perfect matching for bipartite graph with no cycles unique?
Given a balanced bipartite graph that satisfies Hall's theorem (is non singular) then it shown that it has at least one perfect matching.
My question is if the balanced bipartite graph is also ...
- 155
3
votes
0
answers
1k
views
Eigenvalues of adjacency matrix of a connected bipartite graph
Let $G=(V,E)$ is a connected d-regular bipartite graph with the same number of vertices on both sides of the bipartition. It's known that that the largest eigenvalue of its adjacency matrix would be d,...
- 419
5
votes
2
answers
324
views
Efficient way to generate random planar cubic bipartite graphs
3-regular bipartite planar graphs appear in a variety of NP- / #P-complete problems. Suppose one wants to test the complexity of these problems via numerical experiments. Is there an efficient way to ...
- 828
4
votes
1
answer
400
views
Is Permanent $+$-reducible?
Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$.
Is ...
- 13.1k
0
votes
1
answer
217
views
What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?
We know counting perfect matching for bipartite graphs with vertex degree $2$ is in $P$ while counting perfect matching for graphs with vertex degree $3$ is in $\#P$.
We also know there are degree $3$...
- 13.1k
-2
votes
1
answer
323
views
3-Hitting-Set - maximum flow algorithm [closed]
so i'm currently learning for an exam and got in an exercise the following question (a loose translation):
Find an Algorithm that finds the smallest U' ⊆ U that is a solution the 3 HITTING SET ...
1
vote
1
answer
421
views
What is a weakly-simplicial vertex?
While studying chordal bipartite graphs, I have come across weakly simplicial vertices. I have searched for some time to understand what a weakly simplicial vertex is but I haven't succeeded.
A ...
- 33
2
votes
1
answer
177
views
Maximum stable matching/allocation
I checked some papers on two-side stable allocation/matching (marriage, worker/company, doctor/hospital), but has not found any literature on the following problem. Can someone point out if I missed ...
- 119
2
votes
1
answer
283
views
generate a graph with fixed min cut
Is there a constructive way to generate a graph with a fixed min cut equal to $k$?
One approach is to generate a random graph and then try to make edges alterations (additions, deletions, swaps) to ...
- 41
2
votes
0
answers
69
views
Degree distribution of certain subgraphs of a biregular graph
Consider a bipartite graph $G=(X,Y)$, such that the degree of a left node $x \in X$ is $l$, and the degree of a right node $y \in Y$ is $r$. The number of edges is $|E|=|X|l=|Y|r$.
Pick $w$ nodes in ...
- 315
0
votes
1
answer
295
views
Online/approximate weighted and capacitated bipartite matching
I wish to take a look at online/approximate weighted and capacitated bipartite matching problem.
Consider $G=\{L\cup R, E\}$, $|L|=n_1$, $|R|=n_2$, $|E|=m$ and $E\subseteq L\times R$. For each $r_i\...
- 119
1
vote
0
answers
113
views
algorithms for a large submatrix / general factor / quasi-biclique problem?
Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that ...
- 145
1
vote
0
answers
120
views
Algorithm for maximum bipartite matching with arriving edges?
Given a bipartite graph with fixed nodes and incrementally arriving edges, is there any efficient algorithm to compute and update the maximum matching?
- 111
6
votes
1
answer
751
views
Is "two or zero" matching in a bipartite graph NP complete?
I have this problem, which I haven't seen before in the literature: given a bipartite graph and a natural number $k$, can we select at least $k$ of the edges such that each left-hand vertex is ...
- 163
8
votes
2
answers
3k
views
Complexity of counting matchings in a bipartite graph
I might be missing something obvious but I can't find references about the complexity of counting matchings (not perfect matchings) in bipartite graphs. Here is the formal problem:
Input: a bipartite ...
- 9,697
5
votes
1
answer
690
views
Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard?
Given:
A bipartite graph G=(U,V,E)
Integers n and k.
Decision Problem:
Is there a subset of U of size k that has at most
n neighbours?
I am trying to figure out whether this problem is NP-hard (...
- 153
4
votes
1
answer
773
views
Constrained version of vertex cover in a bipartite graph
Let $G(V_1, V_2, E)$ be a bipartite graph such that degree of all the vertices in $V_1$ is bounded by some constant (say) $d$. Now, for given two positive integer $l$ and $k$, we wish to decide if ...
- 639
5
votes
1
answer
2k
views
Assignment problem with multiple workers for each job
I am wondering if there are any results on the following version of the assignment problem. We are given a set of jobs $J$ and a set of workers $W$, and for each job $j$ and worker $w$ we are given ...
5
votes
1
answer
342
views
Sparser Bipartite graphs?
Maximal Planar Bipartite graphs are sparser than maximal planar graphs. For which other classes of graphs are maximal Bipartite members sparser than arbitrary maximal members.
Let $\mathcal{C}$ be a ...
- 2,327
10
votes
1
answer
403
views
Maximum weight "fair" matching
I'm interested in a variant of the maximum weight matching in a graph, which I call "Maximum Fair Matching".
Assume that the graph is full (i.e. $E=V\times V$), has even number of vertices, and that ...
- 9,488