The graph 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 conne ...
. Given a finite sequence
of natural numbers, the problem asks whether there is a labeled
simple 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 deno ...
of this graph.
Solutions
The problem can be solved in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
. One method of showing this uses the
Havel–Hakimi algorithm
The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem. That is, it answers the following question: ''Given a finite list of nonnegative integers in non-increasing order, is there a simple graph such th ...
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 ...
. Alternatively, following the characterization given by the
Erdős–Gallai theorem
The Erdős–Gallai theorem is a result in graph theory, a branch of combinatorial mathematics. It provides one of two known approaches to solving the graph realization problem, i.e. it gives a necessary and sufficient condition for a finite sequen ...
, the problem can be solved by testing the validity of
inequalities.
Other notations
The problem can also be stated in terms of
symmetric matrices
In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally,
Because equal matrices have equal dimensions, only square matrices can be symmetric.
The entries of a symmetric matrix are symmetric with re ...
of zeros and ones. The connection can be seen if one realizes that each graph 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 simp ...
where the column sums and row sums correspond to
. The problem is then sometimes denoted by ''symmetric 0-1-matrices for given row sums''.
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 deno ...
s of
simple bipartite graphs or 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 deno ...
s of
simple directed graphs. The first problem is the so-called
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 bip ...
. 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 problem of constructing a solution for the graph realization problem with the additional constraint that each such solution comes with the same probability was shown to have a
polynomial-time approximation scheme
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
A PTAS is an algorithm which takes an insta ...
for the degree sequences of
regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...
s by Cooper, Martin, and Greenhill.
[.] The general problem is still unsolved.
References
{{DEFAULTSORT:graph realization problem
Computational problems in graph theory