Complexity and Polynomial-Time Approximation Algorithms around the Scaffolding Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2014

Complexity and Polynomial-Time Approximation Algorithms around the Scaffolding Problem

Abstract

We explore in this paper some complexity issues inspired by the contig scaffolding problem in bioinformatics. We focus on the following problem: given an undirected graph with no loop, and a perfect matching on this graph, find a set of cycles and paths covering every vertex of the graph, with edges alternatively in the matching and outside the matching, and satisfying a given constraint on the numbers of cycles and paths. We show that this problem is NP-complete, even in bipartite graphs. We also exhibit non-approximability and polynomial-time approximation results, in the optimization versions of the problem.
No file

Dates and versions

lirmm-01007556 , version 1 (16-06-2014)

Identifiers

Cite

Annie Chateau, Rodolphe Giroudeau. Complexity and Polynomial-Time Approximation Algorithms around the Scaffolding Problem. AlCoB: Algorithms for Computational Biology, Jul 2014, Tarragona, Spain. pp.47-58, ⟨10.1007/978-3-319-07953-0_4⟩. ⟨lirmm-01007556⟩
184 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More