Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases

Mathias Weller, Annie Chateau, Clément Dallard, Rodolphe Giroudeau

Research output: Contribution to journalArticlepeer-review

89 Downloads (Pure)

Abstract

This paper is devoted to new results about the scaffolding problem, an integral problem of genome inference in bioinformatics. The problem consists in finding a collection of disjoint cycles and paths covering a particular graph called the “scaffold graph”. We examine the difficulty and the approximability of the scaffolding problem in special classes of graphs, either close to trees, or very dense. We propose negative and positive results, exploring the frontier between difficulty and tractability of computing and/or approximating a solution to the problem. Also, we explore a new direction through related problems consisting in finding a family of edges having a strong effect on solution weight.
Original languageEnglish
Number of pages33
JournalAlgorithmica
Volume80
Early online date29 Jan 2018
DOIs
Publication statusEarly online - 29 Jan 2018

Keywords

  • graph theory
  • bioinformatics

Fingerprint

Dive into the research topics of 'Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases'. Together they form a unique fingerprint.

Cite this