The parameterized complexity of editing graphs for bounded degeneracy

Luke Mathieson*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

We examine the parameterized complexity of the problem of editing a graph to obtain an r-degenerate graph. We show that for the editing operations vertex deletion and edge deletion, both separately and combined, the problem is W[P]-complete, and remains W[P]-complete even if the input graph is already (r+1)-degenerate, or has maximum degree 2r+1 for all r<2. We also demonstrate fixed-parameter tractability for several Clique based problems when the input graph has bounded degeneracy.

Original languageEnglish
Pages (from-to)3181-3187
Number of pages7
JournalTheoretical Computer Science
Volume411
Issue number34-36
DOIs
Publication statusPublished - 17 Jul 2010

Keywords

  • Combinatorial problems
  • Computational complexity
  • Degenerate graphs
  • Graph editing
  • Parameterized complexity

Fingerprint

Dive into the research topics of 'The parameterized complexity of editing graphs for bounded degeneracy'. Together they form a unique fingerprint.

Cite this