Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Graph editing to a given degree sequence.

Golovach, P.A. and Mertzios, G.B. (2017) 'Graph editing to a given degree sequence.', Theoretical computer science., 665 . pp. 1-12.

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 σ by at most k vertex deletions, 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 2O(k(Δ⁎+k)2)n2log⁡n 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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(361Kb)
Status:Peer-reviewed
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

Export:
Export
Look up in GoogleScholar