Skip to main content

Research Repository

Advanced Search

Graph editing to a given degree sequence

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

Graph editing to a given degree sequence Thumbnail


Authors

P.A. Golovach



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.

Citation

Golovach, P., & Mertzios, G. (2017). Graph editing to a given degree sequence. Theoretical Computer Science, 665, 1-12. https://doi.org/10.1016/j.tcs.2016.12.007

Journal Article Type Article
Acceptance Date Dec 4, 2016
Online Publication Date Dec 23, 2016
Publication Date Feb 22, 2017
Deposit Date Dec 5, 2016
Publicly Available Date Mar 28, 2024
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 665
Pages 1-12
DOI https://doi.org/10.1016/j.tcs.2016.12.007

Files





You might also like



Downloadable Citations