NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs

DOI10.1007/978-3-642-30870-3_29zbMath1330.68113arXiv1110.1510OpenAlexW1789233327WikidataQ59445246 ScholiaQ59445246MaRDI QIDQ5891702

Sepp Hartung, André Nichterlein

Publication date: 14 August 2012

Published in: Lecture Notes in Computer Science, SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1110.1510

zbMATH Keywords

combinatorial algorithmsparameterized complexitystructural parameterizationgraph realization problemsrealizing topological orderings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Related Items (6)

Graph realizations: maximum degree in vertex neighborhoods ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Efficiently Realizing Interval Sequences ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ Realization problems on reachability sequences ⋮ Relaxed and approximate graph realizations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• A theorem on flows in networks
• Zero-one matrices with zero trace
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
• An application of simultaneous diophantine approximation in combinatorial optimization
• On the realization of a (p,s)-digraph with prescribed degrees
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Parametrized complexity theory.
• Algorithms for constructing graphs and digraphs with given valences and factors
• New Races in Parameterized Algorithmics
• Integer Programming with a Fixed Number of Variables
• Dag Realizations of Directed Degree Sequences
• Reflections on Multivariate Algorithmics and Problem Parameterization
• A remark on the existence of finite graphs
• Combinatorial Properties of Matrices of Zeros and Ones
• Minkowski's Convex Body Theorem and Integer Programming
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I

This page was built for publication: NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs