Motivated by problems in comparative genomics and paleogenomics, we study the computational complexity of the Gapped Consecutive-Ones Property ((k,δ)-C1P) Problem: given a binary matrix M and two integers k and δ, decide if the columns of M can be permuted such that each row contains at most k blocks of ones and no two neighboring blocks of ones are separated by a gap of more than δ zeros. The classical C1P decision problem, which is known to be polynomial-time solvable is equivalent to the (1,0)-C1P problem. We extend our earlier results on this problem [C. Chauve, J. Mauch, M. Patterson, On the gapped consecutive-ones property, in: Proceedings of the European Conference on Combinatorics, Graphs Theory and Applications (EuroComb), in: Electronic Notes in Discrete Mathematics, vol. 34, 2009, pp. 121-125] to show that for every k<2,δ<1,(k,δ)≠(2,1), the (k,δ)-C1P Problem is NP-complete, and that for every δ<1, the (∞,δ)-C1P Problem is NP-complete. On the positive side, we also show that if k,δ and the maximum degree of M are constant, the problem is related to the classical Graph Bandwidth Problem and can be solved in polynomial time using a variant of an algorithm of Saxe [J.B. Saxe, Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time, SIAM Journal on Algebraic and Discrete Methods 1 (4) (1980) 363-369]. © 2011 Elsevier B.V. All rights reserved

Mauch, J., Patterson, M., Chauve, C. (2012). Hardness results on the gapped consecutive-ones property problem. DISCRETE APPLIED MATHEMATICS, 160(18), 2760-2768 [10.1016/j.dam.2012.03.019].

Hardness results on the gapped consecutive-ones property problem

Patterson, Murray;
2012

Abstract

Motivated by problems in comparative genomics and paleogenomics, we study the computational complexity of the Gapped Consecutive-Ones Property ((k,δ)-C1P) Problem: given a binary matrix M and two integers k and δ, decide if the columns of M can be permuted such that each row contains at most k blocks of ones and no two neighboring blocks of ones are separated by a gap of more than δ zeros. The classical C1P decision problem, which is known to be polynomial-time solvable is equivalent to the (1,0)-C1P problem. We extend our earlier results on this problem [C. Chauve, J. Mauch, M. Patterson, On the gapped consecutive-ones property, in: Proceedings of the European Conference on Combinatorics, Graphs Theory and Applications (EuroComb), in: Electronic Notes in Discrete Mathematics, vol. 34, 2009, pp. 121-125] to show that for every k<2,δ<1,(k,δ)≠(2,1), the (k,δ)-C1P Problem is NP-complete, and that for every δ<1, the (∞,δ)-C1P Problem is NP-complete. On the positive side, we also show that if k,δ and the maximum degree of M are constant, the problem is related to the classical Graph Bandwidth Problem and can be solved in polynomial time using a variant of an algorithm of Saxe [J.B. Saxe, Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time, SIAM Journal on Algebraic and Discrete Methods 1 (4) (1980) 363-369]. © 2011 Elsevier B.V. All rights reserved
Articolo in rivista - Articolo scientifico
Algorithm; Ancestral genome reconstruction; Computational complexity; Consecutive-ones property; Graph bandwidth; Discrete Mathematics and Combinatorics; Applied Mathematics
English
2012
160
18
2760
2768
open
Mauch, J., Patterson, M., Chauve, C. (2012). Hardness results on the gapped consecutive-ones property problem. DISCRETE APPLIED MATHEMATICS, 160(18), 2760-2768 [10.1016/j.dam.2012.03.019].
File in questo prodotto:
File Dimensione Formato  
hardness_2012.pdf

accesso aperto

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 307.6 kB
Formato Adobe PDF
307.6 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/217373
Citazioni
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
Social impact