# Digraph realization problem > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Digraph_realization_problem > Markdown URL: https://mediated.wiki/source/Digraph_realization_problem.md > Source: https://en.wikipedia.org/wiki/Digraph_realization_problem > Source revision: 1338003022 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{Short description|Decision problem in graph theory}} [[File:Digraph realization.svg|thumb|upright=1.2|A list of pairs, where the digits represent the [indegree](/source/directed_graph) and [outdegree](/source/directed_graph) 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](/source/decision_problem) in [graph theory](/source/graph_theory). Given pairs of nonnegative [integer](/source/integer)s ((a_1,b_1),\ldots,(a_n,b_n)), the problem asks whether there is a labeled [simple directed graph](/source/directed_graph) such that each [vertex](/source/vertex_(graph_theory)) v_i has [indegree](/source/directed_graph) a_i and [outdegree](/source/directed_graph) b_i. ==Solutions== The problem belongs to the complexity class [P](/source/P_(complexity)). Two algorithms are known to prove that. The first approach is given by the [Kleitman–Wang algorithms](/source/Kleitman%E2%80%93Wang_algorithms) constructing a special solution with the use of a [recursive algorithm](/source/Recursion_(computer_science)). The second one is a characterization by the [Fulkerson–Chen–Anstee theorem](/source/Fulkerson%E2%80%93Chen%E2%80%93Anstee_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](/source/matrix_(mathematics)). The connection can be seen if one realizes that each [directed graph](/source/directed_graph) has an [adjacency matrix](/source/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 table](/source/contingency_table)s by ''contingency tables with given marginals''. ==Related problems== Similar problems describe the [degree sequenc](/source/Degree_(graph_theory))es of [simple graphs](/source/Graph_theory), [simple directed graphs](/source/directed_graph) with [loop](/source/directed_graph)s, and [simple bipartite graph](/source/bipartite_graph)s. The first problem is the so-called [graph realization problem](/source/graph_realization_problem). The second and third one are equivalent and are known as the [bipartite realization problem](/source/bipartite_realization_problem). {{harvtxt|Chen|1966}} gives a characterization for [directed multigraphs](/source/Multigraph) with a bounded number of parallel arcs and loops to a given [degree sequence](/source/directed_graph). The additional constraint of the acyclicity of the directed graph is known as ''dag realization''. {{harvtxt|Nichterlein|Hartung|2012}} proved the [NP-complete](/source/NP-complete)ness of this problem. {{harvtxt|Berger|Müller-Hannemann|2011}} showed that the class of [opposed sequences](/source/sequence_(graph_theory)) is in [P](/source/P_(complexity)). 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](/source/Polynomial-time_approximation_scheme) for [regular sequences](/source/sequence_(graph_theory)) by {{harvs|first=Catherine|last=Greenhill|authorlink=Catherine Greenhill|year=2011|txt}} The general problem is still unsolved. ==References== *{{citation | last = Chen | first = Wai-Kai | title = On the realization of a (''p'',''s'')-digraph with prescribed degrees | journal = Journal of the Franklin Institute | volume = 103 | year = 1966 | pages = 406–422 }} *{{citation | last1 = Nichterlein | first1 = André | last2 = Hartung | first2 = Sepp | title = NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs | journal = Journal of the Franklin Institute | volume = 7318 | year = 2012 | pages = 283–292}} *{{citation | last1 = Berger | first1 = Annabell | last2 = Müller-Hannemann | first2 = Matthias | title = Dag Realizations of Directed Degree Sequences | journal = Proceedings of the 18th International Conference on Fundamentals of Computation Theory | year = 2011 | pages = 264–275}} *{{citation | last = Greenhill | first = Catherine | authorlink = Catherine Greenhill | title = A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs | journal = Electronic Journal of Combinatorics |volume=18 | year = 2011}} {{DEFAULTSORT:digraph realization problem}} Category:Computational problems in graph theory --- Adapted from the Wikipedia article [Digraph realization problem](https://en.wikipedia.org/wiki/Digraph_realization_problem) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Digraph_realization_problem?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.