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 labeled simple graph such that $(d_{1},\dots ,d_{n})$ is the degree sequence of this graph.

Solutions

The problem belongs to the complexity class P. Two algorithms can be given to prove that. The first approach is given by the Havel-Hakimi Algorithm constructing a special solution with the use of a recursive algorithm. The second one is a characterization by the Erdős–Gallai theorem, i.e. one has to validate the correctness of $n$ inequalities.

Other notations

The problem can also be stated in terms of symmetric matrices of zeros and ones. The connection can be seen if one realizes that each graph has an adjacency matrix where the column sums and row sums correspond to $(d_{1},\cdots ,d_{n})$. The problem is then sometimes denoted by symmetric 0-1-matrices for given row sums.

Related problems

Similar problems describe the degree sequences of simple bipartite graphs or the degree sequences of simple directed graphs. The first problem is the so-called bipartite realization problem. The second is known as the digraph realization problem. A generalization is the f-factor problem, i.e. for a given graph one searchs for a subgraph possessing a certain degree sequence. The problem uniform sampling a graph to a fixed degree sequence is to construct a solution for the graph realization problem with the additional constraint that each such solution comes with the same probability. This problem was shown to be in FPTAS for regular sequences by Cooper et al. The general problem is still unsolved.

References

• Cooper, Colin; Dyer, Martin; Greenhill, Catherine (2007), Sampling Regular Graphs and a Peer-to-Peer Network, Combinatorics, Probability and Computing, pp. 557–593