### Abstract

We investigate the computational complexity of a combinatorial problem that arises in DNA sequencing by hybridization: The input consists of an integer l together with a set S of words of length k over the four symbols A, C, G, T. The problem is to decide whether there exists a word of length l that contains every word in S at least once as a subword, and does not contain any other subword of length k. The computational complexity of this problem has been open for some time, and it remains open. What we prove is that this problem is polynomial time equivalent to the exact perfect matching problem in bipartite graphs, which is another infamous combinatorial optimization problem of unknown computational complexity.

Original language | English |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science |

Subtitle of host publication | 28th International Workshop, WG 2002 Český Krumlov, Czech Republic, June 13–15, 2002 Revised Papers |

Editors | Gerhard Goos, Juris Hartmanis, Jan van Leeuwen, Ludek Kucera |

Publisher | Springer |

Pages | 13-24 |

ISBN (Electronic) | 978-3-540-36379-8 |

ISBN (Print) | 978-3-540-00331-1 |

DOIs | |

Publication status | Published - 2002 |

Event | 28th International Workshop on Graph-Theoretic Concepts in Computer Science 2002 - Cesky Krumlov, Czech Republic Duration: 13 Jun 2002 → 15 Jun 2002 Conference number: 28 |

### Publication series

Name | Lecture notes in computer science |
---|---|

Volume | 2573 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 28th International Workshop on Graph-Theoretic Concepts in Computer Science 2002 |
---|---|

Abbreviated title | WG 2002 |

Country | Czech Republic |

City | Cesky Krumlov |

Period | 13/06/02 → 15/06/02 |

### Keywords

- METIS-208662

## Fingerprint Dive into the research topics of 'DNA sequencing, Eulerian graphs, and the exact perfect matching problem'. Together they form a unique fingerprint.

## Cite this

Blazewicz, J., Formanowicz, P., Kasprzak, M., Schuurman, P., & Woeginger, G. (2002). DNA sequencing, Eulerian graphs, and the exact perfect matching problem. In G. Goos, J. Hartmanis, J. van Leeuwen, & L. Kucera (Eds.),

*Graph-Theoretic Concepts in Computer Science: 28th International Workshop, WG 2002 Český Krumlov, Czech Republic, June 13–15, 2002 Revised Papers*(pp. 13-24). (Lecture notes in computer science; Vol. 2573). Springer. https://doi.org/10.1007/3-540-36379-3_2