Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Probably Optimal Graph Motifs

Björklund, Andreas LU ; Kaski, Petteri and Kowalik, Lukasz (2013) 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), LIPIcs 20. p.20-31
Abstract
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.
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
[Host publication title missing]
editor
Portier, Natacha and Wilke, Thomas
volume
20
pages
12 pages
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
conference name
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), LIPIcs
conference dates
2013-02-28
external identifiers
  • scopus:84892570565
ISSN
1868-8969
project
Exact algorithms
language
English
LU publication?
yes
id
15e75700-0fe9-4599-922d-0f50e58b1c97 (old id 3560520)
date added to LUP
2016-04-01 12:53:22
date last changed
2022-03-13 20:54:49
@inproceedings{15e75700-0fe9-4599-922d-0f50e58b1c97,
  abstract     = {{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.}},
  author       = {{Björklund, Andreas and Kaski, Petteri and Kowalik, Lukasz}},
  booktitle    = {{[Host publication title missing]}},
  editor       = {{Portier, Natacha and Wilke, Thomas}},
  issn         = {{1868-8969}},
  language     = {{eng}},
  pages        = {{20--31}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  title        = {{Probably Optimal Graph Motifs}},
  volume       = {{20}},
  year         = {{2013}},
}