Computer Science – Computational Complexity
Scientific paper
2011-10-07
Computer Science
Computational Complexity
new author Sepp Hartung, new section with fixed-parameter tractability result; 25 pages, 4 figures
Scientific paper
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 to the given sequence. This realization problem is known to be polynomial-time solvable when the graph is directed or undirected. In contrary, we show NP-completeness for the problem of realizing a given sequence of pairs of positive integers (representing indegrees and outdegrees) with a directed acyclic graph, answering an open question of Berger and M\"uller-Hannemann [FCT 2011]. Furthermore, we classify the problem as fixed-parameter tractable with respect to the parameter "maximum degree".
Hartung Sepp
Nichterlein André
No associations
LandOfFree
NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-133040