Graph editing to a given degree sequence

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

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: Dec 23, 2017
• 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
• Public URL: https://durham-repository.worktribe.com/output/1399097