The bipartite realization problem is a classical

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a branch of

combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...

. Given two finite sequences

(a_1,\dots,a_n)

and

(b_1,\dots,b_n)

of natural numbers, the problem asks whether there is a labeled simple bipartite graph such that

(a_1,\dots,a_n),(b_1,\dots,b_n)

is the

degree sequence In graph theory, the degree (or valency) of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex v is denoted ...

of this bipartite graph.

Solutions

The problem belongs to the complexity class P. This can be proven using the

Gale–Ryser theorem The Gale–Ryser theorem is a result in graph theory and combinatorial matrix theory, two branches of combinatorics. It provides one of two known approaches to solving the bipartite realization problem, i.e. it gives a necessary and sufficient con ...

, i.e., one has to validate the correctness of

n

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 In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

has a biadjacency matrix where the column sums and row sums correspond to

(a_1,\ldots,a_n)

and

(b_1,\ldots,b_n)

. 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 table In statistics, a contingency table (also known as a cross tabulation or crosstab) is a type of table in a matrix format that displays the (multivariate) frequency distribution of the variables. They are heavily used in survey research, business i ...

s by ''contingency tables with given marginals''. A third formulation is in terms of

s of simple directed graphs with at most one loop per vertex. In this case the matrix is interpreted as the

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...

of such a directed graph. When are pairs of non-negative integers ((''a''₁,''b''₁), ..., (''a''_''n'',''b''_''n'')) the indegree-outdegree pairs of a labeled directed graph with at most one loop per vertex?

Related problems

Similar problems describe the

s of simple graphs and simple directed graphs. The first problem is the so-called

graph realization problem The graph realization problem is a decision problem in graph theory. Given a finite sequence (d_1,\dots,d_n) of natural numbers, the problem asks whether there is a labeled simple graph such that (d_1,\dots,d_n) is the degree sequence of this grap ...

. The second is known as the

digraph realization problem The digraph realization problem is a decision problem in graph theory. Given pairs of nonnegative integers ((a_1,b_1),\ldots,(a_n,b_n)), the problem asks whether there is a labeled simple directed graph such that each vertex v_i has indegree a_i an ...

. 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 A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It r ...

for regular sequences by

Catherine Greenhill Catherine Greenhill is an Australian mathematician known for her research on random graphs, combinatorial enumeration and Markov chains. She is a professor of mathematics in the School of Mathematics and Statistics at the University of New Sout ...

(for regular bipartite graphs with a forbidden 1-factor) and for half-regular sequences by Erdős et al. The general problem is still unsolved.

Citations

References

* * * * * {{DEFAULTSORT:digraph realization problem Computational problems in graph theory Bipartite graphs