Publication details for Dr George MertziosGolovach, P.A. & Mertzios, G.B. (2017). Graph editing to a given degree sequence. Theoretical Computer Science 665: 1-12.
- Publication type: Journal Article
- ISSN/ISBN: 0304-3975
- DOI: 10.1016/j.tcs.2016.12.007
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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 σ by at most k vertex deletions, edge deletions and edge additions. We show that the problem is W-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 2O(k(Δ⁎+k)2)n2logn for n -vertex graphs, where Δ⁎=maxσ, i.e., the problem is FPT when parameterized by k+Δ⁎. We also show that Editing to a Graph with a Given Degree Sequence has a polynomial kernel when parameterized by k+Δ⁎ if only edge additions are allowed, and there is no polynomial kernel unless NP⊆co-NP/poly for all other combinations of the allowed editing operations.