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. (2016) 'Graph editing to a given degree sequence.', in Computer science – Theory and applications : 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016. Proceedings. Cham: Springer, pp. 177-191. Lecture notes in computer science. (9691).

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 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 2O(k(Δ+k)2)n2logn2O(k(Δ+k)2)n2log⁡n for n-vertex graphs, where Δ=maxσΔ=maxσ, i.e., the problem is FPT when parameterized by k+Δk+Δ. We also show that Editing to a Graph with a Given Degree Sequence has a polynomial kernel when parameterized by k+Δk+Δ if only edge additions are allowed, and there is no polynomial kernel unless NP⊆coNP/polyNP⊆coNP/poly for all other combinations of allowed editing operations.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
(318Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1007/978-3-319-34171-2_13
Publisher statement:The final publication is available at Springer via https://doi.org/10.1007/978-3-319-34171-2_13
Date accepted:11 February 2016
Date deposited:18 March 2016
Date of first online publication:31 May 2016
Date first made open access:31 May 2017

Save or Share this output

Export:
Export
Look up in GoogleScholar