Editing graphs to satisfy degree constraints: a parameterized approach

DOI10.1016/j.jcss.2011.02.001zbMath1242.68124MaRDI QIDQ414866

Luke Mathieson, Stefan Szeider

Publication date: 11 May 2012

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.2011.02.001

zbMATH Keywords

computational complexity; parameterized complexity; kernelization; graph editing; general factor; regular subgraph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, Editing to Connected F-Degree Graph, Graph Editing to a Given Degree Sequence, The complexity of gerrymandering over graphs: paths and trees, The complexity of gerrymandering over graphs: paths and trees, Disconnected matchings, How hard is safe bribery?, A survey of parameterized algorithms and the complexity of edge modification, Win-win kernelization for degree sequence completion problems, Prices matter for the parameterized complexity of shift bribery, Tight complexity bounds for FPT subgraph problems parameterized by the clique-width, Parameterized complexity of three edge contraction problems with degree constraints, Circulant graphs and GCD and LCM of subsets, Graph editing to a given degree sequence, Graph editing problems with extended regularity constraints, Editing to a planar graph of given degrees, Editing to Eulerian graphs, A parameterized algorithmics framework for degree sequence completion problems in directed graphs, Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming, Parameterized algorithms and kernels for almost induced matching, An improved linear kernel for the cycle contraction problem, A refined complexity analysis of degree anonymization in graphs, Editing to a graph of given degrees, Editing to a connected graph of given degrees, The complexity of degree anonymization by graph contractions, Fixed-parameter tractable distances to sparse graph classes, Parameterized complexity of firefighting, Building large \(k\)-cores from sparse graphs, Almost Induced Matching: Linear Kernels and Parameterized Algorithms, Editing to a Planar Graph of Given Degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of regular subgraph recognition
• On the fixed-parameter tractability of parameterized model-checking problems
• On the parameterized complexity of multiple-interval graph problems
• Parameterized complexity of finding regular induced subgraphs
• A note on the complexity of finding regular subgraphs
• General factors of graphs
• Matching theory
• NP-completeness of some generalizations of the maximum matching problem
• Graph factors
• Induced matchings
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• General antifactors of graphs
• On locating cubic subgraphs in bounded-degree connected bipartite graphs
• Antifactors of graphs
• Finding a \(\Delta\)-regular supergraph of minimum order
• Spanning subgraphs with specified valencies
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Finding regular subgraphs in both arbitrary and planar graphs
• Maximum \(k\)-regular induced subgraphs
• Parametrized complexity theory.
• Tight lower bounds for certain parameterized NP-hard problems
• Deciding first-order properties of locally tree-decomposable structures
• Kernels: Annotated, Proper and Induced
• An algorithmic proof of Tutte's f-factor theorem
• Paths, Trees, and Flowers
• Parameterized Graph Editing with Chosen Vertex Degrees
• The factorization of graphs. II
• A Short Proof of the Factor Theorem for Finite Graphs
• Three‐regular subgraphs of four‐regular graphs
• Combinatorial optimization. Theory and algorithms.