Editing graphs to satisfy degree constraints

A parameterized approach

Luke Mathieson, Stefan Szeider*

*Corresponding author for this work

Research output: Contribution to journalArticle

37 Citations (Scopus)

Abstract

We study a wide class of graph editing problems that ask whether a given graph can be modified to satisfy certain degree constraints, using a limited number of vertex deletions, edge deletions, or edge additions. The problems generalize several well-studied problems such as the General Factor Problem and the Regular Subgraph Problem. We classify the parameterized complexity of the considered problems taking upper bounds on the number of editing steps and the maximum degree of the resulting graph as parameters.

Original languageEnglish
Pages (from-to)179-191
Number of pages13
JournalJournal of Computer and System Sciences
Volume78
Issue number1
DOIs
Publication statusPublished - Jan 2012

Keywords

  • Computational complexity
  • General factor
  • Graph editing
  • Kernelization
  • Parameterized complexity
  • Regular subgraph

Fingerprint Dive into the research topics of 'Editing graphs to satisfy degree constraints: A parameterized approach'. Together they form a unique fingerprint.

  • Cite this