Abstract: We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence, where the aim is to obtain a graph with a given degree sequence sigma by at most k vertex or edge deletions and edge additions. We show that the problem is W[1]-hard when parameterized by k for any combination of the allowed editing operations. From the positive side, we show that the problem can be solved in time 2^{O(k(Delta+k)^2)}n^2 log n for n-vertex graphs, where Delta=max sigma, i.e., the problem is FPT when parameterized by k+Delta. We also show that Editing to a Graph with a Given Degree Sequence has a polynomial kernel when parameterized by k+Delta if only edge additions are allowed, and there is no polynomial kernel unless NPsubseteq coNP/poly for all other combinations of allowed editing operations.
Recommendations
- Graph editing to a given degree sequence
- Editing to a connected graph of given degrees
- Editing to a connected graph of given degrees
- Editing to a planar graph of given degrees
- Editing to a planar graph of given degrees
- Editing to connected \(f\)-degree graph
- Editing to Connected F-Degree Graph
- Parameterized Graph Editing with Chosen Vertex Degrees
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- A refined complexity analysis of degree anonymization in graphs
- Color-coding
- Editing graphs to satisfy degree constraints: a parameterized approach
- Editing to Eulerian graphs
- Editing to a connected graph of given degrees
- Editing to a planar graph of given degrees
- Emergence of Scaling in Random Networks
- Fundamentals of parameterized complexity
- General factors of graphs
- Kernelization Lower Bounds by Cross-Composition
- Parameterized algorithms
- Parameterized complexity of Eulerian deletion problems
- Parameterized complexity of even/odd subgraph problems
- Parameterized complexity of finding regular induced subgraphs
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- The Complexity of Finding a Large Subgraph under Anonymity Constraints
- The complexity of degree anonymization by graph contractions
- The complexity of degree anonymization by vertex addition
- The spanning subgraphs of eulerian graphs
- Win-win kernelization for degree sequence completion problems
Cited in
(13)- Editing to a connected graph of given degrees
- A parameterized algorithmics framework for degree sequence completion problems in directed graphs
- Parameterized Graph Editing with Chosen Vertex Degrees
- Edge-editing to a dense and a sparse graph class
- Editing graphs to satisfy degree constraints: a parameterized approach
- A survey of parameterized algorithms and the complexity of edge modification
- A parameterized algorithmics framework for degree sequence completion problems in directed graphs
- Graph editing to a fixed target
- Dividing splittable goods evenly and with limited fragmentation
- The parameterized complexity of editing graphs for bounded degeneracy
- Graph editing to a given degree sequence
- Editing to a connected graph of given degrees
- Editing to Connected F-Degree Graph
This page was built for publication: Graph editing to a given degree sequence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507592)
