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 ...
in
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
and
of natural numbers, the problem asks whether there is a labeled
simple bipartite graph such that
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
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
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 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
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 ...
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''
1,''b''
1), ..., (''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
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 ...
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