The digraph realization problem is a
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 conn ...
. Given pairs of nonnegative
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s
, the problem asks whether there is a labeled
simple directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
such that each
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
*Vertex (computer graphics), a data structure that describes the position ...
has
indegree
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
and
outdegree
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pai ...
.
Solutions
The problem belongs to the complexity class
P. Two algorithms are known to prove that. The first approach is given by the
Kleitman–Wang algorithms
The Kleitman–Wang algorithms are two different algorithms in graph theory solving the digraph realization problem, i.e. the question if there exists for a finite list of nonnegative integer pairs a simple directed graph such that its degree sequ ...
constructing a special solution with the use of a
recursive algorithm
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves ...
. The second one is a characterization by the
Fulkerson–Chen–Anstee theorem The Fulkerson–Chen–Anstee theorem is a result in graph theory, a branch of combinatorics. It provides one of two known approaches solving the digraph realization problem, i.e. it gives a necessary and sufficient condition for pairs of nonnegativ ...
, i.e. one has to validate the correctness of
inequalities.
Other Notations
The problem can also be stated in terms of zero-one
matrices
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
. The connection can be seen if one realizes that each
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pai ...
has an
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 simple ...
where the column sums and row sums correspond to
and
. Note that the diagonal of the matrix only contains zeros. The problem is then often denoted by ''0-1-matrices for given row and column sums''. In the classical literature the problem was sometimes be 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 ...
s by ''contingency tables with given marginals''.
Related problems
Similar problems describe the
degree sequences of
simple graphs,
simple directed graphs with
loop
Loop or LOOP may refer to:
Brands and enterprises
* Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live
* Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets
* Loop Mobile, ...
s, and
simple bipartite 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 and third one are equivalent and are known as the
bipartite realization problem The bipartite realization problem is a classical decision problem in graph theory, a branch of combinatorics. 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 bipa ...
. gives a characterization for
directed multigraphs with a bounded number of parallel arcs and loops to a given
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 ...
. The additional constraint of the acycilicity of the directed graph is known as ''dag realization''. proved the
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
ness of this problem. showed that the class of
opposed sequences is in
P. The problem ''uniform sampling a directed graph to a fixed degree sequence'' is to construct a solution for the digraph realization problem with the additional constraint that such each 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. I ...
for
regular sequences by The general problem is still unsolved.
References
*
*
*
*
{{DEFAULTSORT:digraph realization problem
Computational problems in graph theory