Graph editing to a given degree sequence
From MaRDI portal
Publication:507592
DOI10.1016/J.TCS.2016.12.007zbMATH Open1356.68098arXiv1601.03174OpenAlexW4210637083MaRDI QIDQ507592FDOQ507592
Authors: Petr A. Golovach, George B. Mertzios 
Publication date: 6 February 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1601.03174
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
- Emergence of Scaling in Random Networks
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- Parameterized complexity of finding regular induced subgraphs
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Title not available (Why is that?)
- Color-coding
- Parameterized algorithms
- Kernelization Lower Bounds by Cross-Composition
- The spanning subgraphs of eulerian graphs
- General factors of graphs
- A refined complexity analysis of degree anonymization in graphs
- Editing to a connected graph of given degrees
- Editing graphs to satisfy degree constraints: a parameterized approach
- Editing to Eulerian graphs
- Parameterized complexity of even/odd subgraph problems
- Parameterized complexity of Eulerian deletion problems
- The Complexity of Finding a Large Subgraph under Anonymity Constraints
- The complexity of degree anonymization by graph contractions
- Win-win kernelization for degree sequence completion problems
- Editing to a planar graph of given degrees
- The complexity of degree anonymization by vertex addition
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
- Dividing splittable goods evenly and with limited fragmentation
- Graph editing to a fixed target
- 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)
