Recognizing DNA graphs is difficult

Rudi Pendavingh, Petra Schuurman, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)
97 Downloads (Pure)


DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. In this paper, we prove the NP-hardness of various recognition problems for subgraphs of De Bruijn graphs; in particular, the recognition of DNA graphs is shown to be NP-hard. As a consequence, two open questions from a recent paper by B a ewicz et al. (Discrete Appl. Math. 98, (1999) 1) are answered in the negative.
Original languageEnglish
Pages (from-to)85-94
Number of pages10
JournalDiscrete applied mathematics
Issue number1
Publication statusPublished - 2003


  • Recognition algorithm
  • NP-hardness
  • Graph Theory
  • De Bruijn graph
  • DNA computing
  • DNA graphs
  • Computational Complexity


Dive into the research topics of 'Recognizing DNA graphs is difficult'. Together they form a unique fingerprint.

Cite this