The parameterized complexity of editing graphs for bounded degeneracy

Luke Mathieson

doi:10.1016/j.tcs.2010.05.015

The parameterized complexity of editing graphs for bounded degeneracy

Luke Mathieson^*

^*Corresponding author for this work

Faculty of Science and Engineering

Research output: Contribution to journal › Article › peer-review

16 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 language	English
Pages (from-to)	3181-3187
Number of pages	7
Journal	Theoretical Computer Science
Volume	411
Issue number	34-36
DOIs	https://doi.org/10.1016/j.tcs.2010.05.015
Publication status	Published - 17 Jul 2010

Keywords

Combinatorial problems
Computational complexity
Degenerate graphs
Graph editing
Parameterized complexity

Access to Document

10.1016/j.tcs.2010.05.015

Cite this

@article{80e9f98a10c043a0aeb27289f8ef6f62,

title = "The parameterized complexity of editing graphs for bounded degeneracy",

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.",

keywords = "Combinatorial problems, Computational complexity, Degenerate graphs, Graph editing, Parameterized complexity",

author = "Luke Mathieson",

year = "2010",

month = jul,

day = "17",

doi = "10.1016/j.tcs.2010.05.015",

language = "English",

volume = "411",

pages = "3181--3187",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "34-36",

}

TY - JOUR

T1 - The parameterized complexity of editing graphs for bounded degeneracy

AU - Mathieson, Luke

PY - 2010/7/17

Y1 - 2010/7/17

N2 - 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.

AB - 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.

KW - Combinatorial problems

KW - Computational complexity

KW - Degenerate graphs

KW - Graph editing

KW - Parameterized complexity

UR - https://www.scopus.com/pages/publications/77955425456

U2 - 10.1016/j.tcs.2010.05.015

DO - 10.1016/j.tcs.2010.05.015

M3 - Article

AN - SCOPUS:77955425456

SN - 0304-3975

VL - 411

SP - 3181

EP - 3187

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 34-36

ER -

The parameterized complexity of editing graphs for bounded degeneracy

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this