The bipartite realization problem is a classical decision problem in graph theory, a branch of combinatorics. Given two finite sequences
Contents
Solutions
The problem belongs to the complexity class P. This can be proven using the Gale–Ryser theorem, i.e. one has to validate the correctness of
Other notations
The problem can also be stated in terms of zero-one matrices. The connection can be seen if one realizes that each bipartite graph has an biadjacency matrix where the column sums and row sums correspond to
Related problems
Similar problems describe the degree sequences of simple graphs and simple directed graphs. The first problem is the so-called graph realization problem. The second is known as the digraph realization problem. The bipartite realization problem is equivalent to the question, if there exists a labeled bipartite subgraph of a complete bipartite graph to a given degree sequence. The hitchcock problem asks for such a subgraph minimizing the sum of the costs on each edge which are given for the complete bipartite graph. A further generalization is the f-factor problem for bipartite graphs, i.e. for a given bipartite graph one searches for a subgraph possessing a certain degree sequence. The problem uniform sampling a bipartite graph to a fixed degree sequence is to construct a solution for the bipartite realization problem with the additional constraint that each such solution comes with the same probability. This problem was shown to be in FPTAS for regular sequences by Kannan et al. and for half-regular sequences by Miklós et al. The general problem is still unsolved.