Graph editing to a given degree sequence

Golovach, P.A.; Mertzios, G.B.

doi:10.1007/978-3-319-34171-2_13

Graph editing to a given degree sequence

Golovach, P.A.; Mertzios, G.B.

Authors

P.A. Golovach

Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor

Contributors

A.S Kulikov
Editor

G. Woeginger
Editor

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.

Citation

Golovach, P., & Mertzios, G. (2016). Graph editing to a given degree sequence. In A. Kulikov, & G. Woeginger (Eds.), Computer science – Theory and applications : 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016. Proceedings (177-191). https://doi.org/10.1007/978-3-319-34171-2_13

Conference Name	11th International Computer Science Symposium in Russia.
Conference Location	St. Petersburg, Russia
Start Date	Jun 9, 2016
End Date	Jun 13, 2016
Acceptance Date	Feb 11, 2016
Online Publication Date	May 31, 2016
Publication Date	May 31, 2016
Deposit Date	Feb 12, 2016
Publicly Available Date	May 31, 2017
Pages	177-191
Series Title	Lecture notes in computer science
Series Number	9691
Series ISSN	0302-9743,1611-3349
Book Title	Computer science – Theory and applications : 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016. Proceedings.
ISBN	9783319341705
DOI	https://doi.org/10.1007/978-3-319-34171-2_13
Public URL	https://durham-repository.worktribe.com/output/1151029
Additional Information	Conference Date: 9-13 June 2016