Digraph realization problem

and outdegree of a given vertex respectively.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 .

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 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.

Similar problems describe the degree sequences of simple graphs, simple directed graphs with loops, and simple bipartite graphs. The first problem is the so-called graph realization problem.

The second and third one are equivalent and are known as the bipartite realization problem. gives a characterization for directed multigraphs with a bounded number of parallel arcs and loops to a given degree sequence. The additional constraint of the acyclicity of the directed graph is known as dag realization. proved the NP-completeness 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 for regular sequences by The general problem is still unsolved.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1338003022 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001338003022 · captured 1770913263.0 · version history

Cite this page as: encyclopegia.org, “Digraph realization problem”, snapshot enwiki-001338003022. https://encyclopegia.org/a/digraph-realization-problem

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.