A complexity and approximation framework for the maximization scaffolding problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Theoretical Computer Science Year : 2015

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.

Dates and versions

lirmm-01219622 , version 1 (22-10-2015)

Identifiers

Cite

Annie Chateau, Rodolphe Giroudeau. A complexity and approximation framework for the maximization scaffolding problem. Theoretical Computer Science, 2015, 595, pp.92-106. ⟨10.1016/j.tcs.2015.06.023⟩. ⟨lirmm-01219622⟩
155 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More