{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T01:38:56Z","timestamp":1787362736775,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>In graph realization problems, one is given a degree sequence and the task is to decide whether there is a graph whose vertex degrees match the given sequence. This realization problem is known to be polynomial-time solvable when the graph is directed or undirected. In contrast, we show NP-completeness for the problem of realizing a given sequence of pairs of nonnegative integers (representing in- and outdegrees) with a directed acyclic graph (DAG), answering an open question of Berger and M\u00fcller-Hannemann. Furthermore, we classify the problem as fixed-parameter tractable with respect to the parameter \u201cmaximum degree.\u201d Investigating sparse and dense settings, we show that the problem remains NP-hard even if the realizing DAG (precisely, the underlying undirected graph) can be transformed into a clique (a tree) by adding (deleting) a constant fraction of the arcs. In contrast, if at most $k$ arcs have to be inserted, respectively, removed to obtain a clique or a tree in the underlying undirected graph, then the problem becomes fixed-parameter tractable with respect to $k$.<\/jats:p>","DOI":"10.1137\/130935756","type":"journal-article","created":{"date-parts":[[2015,10,22]],"date-time":"2015-10-22T10:34:30Z","timestamp":1445510070000},"page":"1931-1960","source":"Crossref","is-referenced-by-count":5,"title":["NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs"],"prefix":"10.1137","volume":"29","author":[{"given":"Sepp","family":"Hartung","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,10,22]]},"reference":[{"key":"atypb1","unstructured":"A. Berger,\n                      Directed Degree Sequences\n                      , Ph.D. thesis, Institut fu\u0308r Informatik, Martin-Luther-Universita\u0308t Halle-Wittenberg, Halle, Germany, 2011."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22953-4_23"},{"key":"atypb3","first-page":"51","author":"Berger A.","year":"2012","journal-title":"New York"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(66)90301-2"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Springer, New York, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb6","first-page":"264","volume":"11","author":"Erdo\u0308s P.","year":"1960","journal-title":"Math. Lapok"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.04.008"},{"key":"atypb8","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Springer, New York, 2006."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579200"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1960.10.831"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1957.7.1073"},{"key":"atypb12","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, San Francisco 1979."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/0110037"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.21136\/CPM.1955.108220"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.05.004"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90037-X"},{"key":"atypb18","first-page":"19","author":"Komusiewicz C.","year":"2012","journal-title":"New York"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2010.07.003"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,\n                      Invitation to Fixed-Parameter Algorithms\n                      , Oxford University Press, Oxford, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"atypb22","first-page":"17","author":"Niedermeier R.","year":"2010","journal-title":"Germany"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1957-044-3"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130935756","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:46:59Z","timestamp":1787320019000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130935756"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130935756"],"URL":"https:\/\/doi.org\/10.1137\/130935756","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}