Digraph realization problem

From Wikipedia, the free encyclopedia

A list of pairs, where the digits represent the indegree and outdegree of a given vertex respectively. The problem asks whether a given list of pairs can be used to construct a graph, and for the list above, the answer is yes.

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}$ and outdegree $b_{i}$ .

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 constructing a special solution with the use of a recursive algorithm. The second one is a characterization by the Fulkerson–Chen–Anstee theorem, 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 directed graph has an adjacency matrix where the column sums and row sums correspond to $(a_{1},\cdots ,a_{n})$ and $(b_{1},\ldots ,b_{n})$ . 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 stated in the context of contingency tables by contingency tables with given marginals.

Related problems

References

Related Articles

Wikiwand AI