Incremental problems in the parameterized complexity setting

Bernard Mans*, Luke Mathieson

*Corresponding author for this work

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Dynamic systems are becoming steadily more important with the profusion of mobile and distributed computing devices. Coincidentally incremental computation is a natural approach to deal with ongoing changes. We explore incremental computation in the parameterized complexity setting and show that incrementalization leads to non-trivial complexity classifications. Interestingly, some incremental versions of hard problems become tractable, while others remain hard. Moreover tractability or intractability is not a simple function of the problem’s static complexity, every level of the W-hierarchy exhibits complete problems with both tractable and intractable incrementalizations. For problems that are already tractable in their static form, we also show that incrementalization can lead to interesting algorithms, improving upon the trivial approach of using the static algorithm at each step.

Original languageEnglish
Pages (from-to)3-19
Number of pages17
JournalTheory of Computing Systems
Volume60
Issue number1
DOIs
Publication statusPublished - 1 Jan 2017

Keywords

  • Algorithm complexity
  • Incremental computation
  • Kernelization
  • Parameterized complexity
  • Tractability

Fingerprint Dive into the research topics of 'Incremental problems in the parameterized complexity setting'. Together they form a unique fingerprint.

  • Cite this