The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Probably Optimal Graph Motifs

På svenska

Author

  • Andreas Björklund
  • Petteri Kaski
  • Lukasz Kowalik

Editor

  • Natacha Portier
  • Thomas Wilke

Summary, in English

We show an O^*(2^k)-time polynomial space algorithm for the k-sized Graph Motif problem. We also introduce a new optimization variant of the problem, called Closest Graph Motif and solve it within the same time bound. The Closest Graph Motif problem encompasses several previously studied optimization variants, like Maximum Graph Motif, Min-Substitute, and Min-Add. Moreover, we provide a piece of evidence that our result might be essentially tight: the existence of an O^*((2-epsilon)^k)-time algorithm for the Graph Motif problem implies an ((2-epsilon')^n)-time algorithm for Set Cover.

Publishing year

2013

Language

English

Pages

20-31

Publication/Series

[Host publication title missing]

Volume

20

Document type

Conference paper

Publisher

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Topic

  • Computer Science

Conference name

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), LIPIcs

Conference date

2013-02-28

Status

Published

Project

  • Exact algorithms

Research group

  • Algorithms

ISBN/ISSN/Other

  • ISSN: 1868-8969