### Page Content

### to Navigation

## On the Computational Complexity of Realizing Degree Sequences as Directed Acyclic Graphs

**André Nichterlein (TU Berlin)**

We study graph realization problems where a degree sequence is given and the task is to decide whether there is a graph whose vertex degrees match to the given sequence. Realizing a given degree sequence as undirected or directed graph is known to be polynomial-time solvable. In contrary, we show NP-hardness for the problem of realizing a given sequence of pairs of positive integers (representing indegree and outdegree) with a directed acyclic graph, answering an open question of Berger and Müller-Hannemann [FCT 2011]. Furthermore, we classify the problem as fixed-parameter tractable with respect to the maximal degree.

date | speaker | location | language |
---|---|---|---|

17.11.2011 16:15 | André Nichterlein | FR 6510 | german/ english* |

* Language is depending on the audience.