A complexity and approximation framework for the maximization scaffolding problem

Annie Château 1 Rodolphe Giroudeau 2
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01219622
Contributeur : Annie Chateau <>
Soumis le : jeudi 22 octobre 2015 - 21:59:30
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

Collections

Citation

Annie Château, Rodolphe Giroudeau. A complexity and approximation framework for the maximization scaffolding problem. Theoretical Computer Science, Elsevier, 2015, 595, pp.92-106. 〈http://www.sciencedirect.com/science/article/pii/S0304397515005332〉. 〈10.1016/j.tcs.2015.06.023〉. 〈lirmm-01219622〉

Partager

Métriques

Consultations de la notice

69