Bipartite realization problem
From Wikipedia, the free encyclopedia
The bipartite realization problem is a classical decision problem in graph theory, a branch of combinatorics. Given two finite sequences and of natural numbers with , the problem asks whether there is a labeled simple bipartite graph such that is the degree sequence of this bipartite graph.
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 inequalities.
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 a biadjacency matrix where the column sums and row sums correspond to and . The problem is then often denoted by 0-1-matrices for given row and column sums. In the classical literature the problem was sometimes stated in the context of contingency tables by contingency tables with given marginals. A third formulation is in terms of degree sequences of simple directed graphs with at most one loop per vertex. In this case the matrix is interpreted as the adjacency matrix of such a directed graph. When are pairs of non-negative integers ((a1,b1), ..., (an,bn)) the indegree-outdegree pairs of a labeled directed graph with at most one loop per vertex?
