 |
HAL-LIRMM - Open Archive |  |
Journal articles
A complexity and approximation framework for the maximization 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 planar bipartite graphs. Moreover, we show that there is no subexponential-time algorithm for several related problems unless the Exponential-Time Hypothesis fails. Lastly, we also design two polynomial-time approximation algorithms for complete graphs.
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01219622
Contributor : Annie Chateau Connect in order to contact the contributor
Submitted on : Thursday, October 22, 2015 - 9:59:30 PM
Last modification on : Monday, October 11, 2021 - 1:24:07 PM
Contributor : Annie Chateau Connect in order to contact the contributor
Submitted on : Thursday, October 22, 2015 - 9:59:30 PM
Last modification on : Monday, October 11, 2021 - 1:24:07 PM
Links full text
