Win-win kernelization for degree sequence completion problems

DOI10.1016/j.jcss.2016.03.009zbMath1345.68156MaRDI QIDQ295647

Rolf Niedermeier, André Nichterlein, Vincent Froese

Publication date: 13 June 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2016.03.009

zbMATH Keywords

computational complexity; data reduction; NP-hardness; \(f\)-factors; lower bounds for problem kernels; polynomial problem kernels

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

A survey of parameterized algorithms and the complexity of edge modification, Editing to a planar graph of given degrees, A parameterized algorithmics framework for degree sequence completion problems in directed graphs, Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Editing graphs to satisfy degree constraints: a parameterized approach
• Kernel bounds for disjoint cycles and disjoint paths
• A generalization of Nemhauser and Trotter's local optimization theorem
• Advice classes of parametrized tractability
• Parameterized complexity of finding regular induced subgraphs
• General factors of graphs
• Matching theory
• The splittance of a graph
• Linear recognition of pseudo-split graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• A refined complexity analysis of degree anonymization in graphs
• Editing to a graph of given degrees
• Parametrized complexity theory.
• Recognition of Unigraphs through Superposition of Graphs
• New Races in Parameterized Algorithmics
• Editing to a Connected Graph of Given Degrees
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
• A Note on Unigraphic Sequences
• Graph Classes: A Survey
• Kernelization Lower Bounds by Cross-Composition
• (Meta) Kernelization
• Graph-Theoretic Concepts in Computer Science
• Complexity classification of some edge modification problems
• Finding large degree-anonymous subgraphs is hard