Golovach, P.A. and Mertzios, G.B. (2017) 'Graph editing to a given degree sequence.', Theoretical computer science., 665 . pp. 1-12.
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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (361Kb)
|Publisher Web site:||https://doi.org/10.1016/j.tcs.2016.12.007|
|Publisher statement:||© 2016 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
|Date accepted:||04 December 2016|
|Date deposited:||05 December 2016|
|Date of first online publication:||23 December 2016|
|Date first made open access:||23 December 2017|
Save or Share this output
|Look up in GoogleScholar|