D. Aguiar and S. Istrail, HapCompass: A Fast Cycle Basis Algorithm for Accurate Haplotype Assembly of Sequence Data, Journal of Computational Biology, vol.19, issue.6, pp.577-590, 2012.
DOI : 10.1089/cmb.2012.0084

V. Bansal and V. Bafna, HapCUT: an efficient and accurate algorithm for the haplotype assembly problem, Bioinformatics, vol.24, issue.16, pp.153-159, 2008.
DOI : 10.1093/bioinformatics/btn298

P. Bonizzoni, D. Vedova, G. Dondi, R. Li, and J. , The Haplotyping problem: An overview of computational models and solutions, Journal of Computer Science and Technology, vol.710, issue.5, pp.675-688, 2003.
DOI : 10.1007/BF02945456

B. Browning and S. Browning, Haplotypic analysis of Wellcome Trust Case Control Consortium data, Human Genetics, vol.316, issue.3, pp.273-280, 2008.
DOI : 10.1007/s00439-008-0472-1
URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2384233

Z. Z. Chen, F. Deng, and L. Wang, Exact algorithms for haplotype assembly from whole-genome sequence data, Bioinformatics, vol.29, issue.16, pp.1938-1983, 2013.
DOI : 10.1093/bioinformatics/btt349

R. Cilibrasi, L. Van-iersel, S. Kelk, and J. Tromp, The Complexity of the Single Individual SNP Haplotyping Problem, Algorithmica, vol.49, issue.1, pp.13-36, 2007.
DOI : 10.1007/s00453-007-0029-z

J. Duitama, T. Huebsch, G. Mcewen, E. Suk, and M. R. Hoehe, ReFHap, Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology, BCB '10, pp.160-169, 2010.
DOI : 10.1145/1854776.1854802

P. Fouilhoux and A. Mahjoub, Solving VLSI design and DNA sequencing problems using bipartization of graphs, Computational Optimization and Applications, vol.291, issue.2, pp.749-781, 2012.
DOI : 10.1007/s10589-010-9355-1
URL : https://hal.archives-ouvertes.fr/hal-01185262

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

N. Garg, V. V. Vazirani, and M. Yannakakis, Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, vol.25, issue.2, pp.235-251, 1996.
DOI : 10.1137/S0097539793243016
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.3217

J. Guo, J. Gramm, F. Hüffner, R. Niedermeier, and S. Wernicke, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Journal of Computer and System Sciences, vol.72, issue.8, pp.1386-1396, 2006.
DOI : 10.1016/j.jcss.2006.02.001
URL : http://doi.org/10.1016/j.jcss.2006.02.001

B. V. Halldórsson, D. Aguiar, and S. Istrail, HAPLOTYPE PHASING BY MULTI-ASSEMBLY OF SHARED HAPLOTYPES: PHASE-DEPENDENT INTERACTIONS BETWEEN RARE VARIANTS, pp.88-99, 2011.
DOI : 10.1142/9789814335058_0010

D. He, A. Choi, K. Pipatsrisawat, A. Darwiche, and E. Eskin, Optimal algorithms for haplotype assembly from whole-genome sequence data, Bioinformatics, vol.26, issue.12, pp.183-190, 2010.
DOI : 10.1093/bioinformatics/btq215
URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2881399

Y. Jiao, J. Xu, and M. Li, On the k-Closest Substring and k-Consensus Pattern Problems, CPM. LNCS, pp.130-144, 2004.
DOI : 10.1007/978-3-540-27801-6_10
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.9205

S. Khot, On the power of unique 2-prover 1-round games, pp.767-775, 2002.

J. M. Kleinberg, C. H. Papadimitriou, and P. Raghavan, Segmentation problems, pp.473-482, 1998.

G. Lancia, V. Bafna, S. Istrail, R. Lippert, and R. Schwartz, SNPs Problems, Complexity, and Algorithms, ESA. LNCS, pp.182-193, 2001.
DOI : 10.1007/3-540-44676-1_15

R. Lippert, R. Schwartz, G. Lancia, and S. Istrail, Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem, Briefings in Bioinformatics, vol.3, issue.1, pp.23-31, 2002.
DOI : 10.1093/bib/3.1.23
URL : http://bib.oxfordjournals.org/cgi/content/short/3/1/23

R. Ostrovsky and Y. Rabani, Polynomial-time approximation schemes for geometric min-sum median clustering, Journal of the ACM, vol.49, issue.2, pp.139-156, 2002.
DOI : 10.1145/506147.506149

M. Patterson, T. Marschall, N. Pisanti, L. Van-iersel, L. Stougie et al., WhatsHap: Haplotype Assembly for Future-Generation Sequencing Reads, RECOMB. LNCS, pp.237-249, 2014.
DOI : 10.1007/978-3-319-05269-4_19
URL : https://hal.archives-ouvertes.fr/hal-01225988

B. A. Reed, K. Smith, and A. Vetta, Finding odd cycle transversals, Operations Research Letters, vol.32, issue.4, pp.299-301, 2004.
DOI : 10.1016/j.orl.2003.10.009
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.6357