Graph motif in O*(2^k) time by narrow sieves by Lukasz Kowalik.
Abstract:
We show an O*(2^k)-time polynomial space algorithm for the Graph Motif problem. Moreover, we show an 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 O((2-\epsilon’)^n)-time algorithm for Set Cover.
The assault on graph problems continues!
It does make me wonder: Is there a comparison listing of graph software/databases and the algorithms they support?
It is one thing to support arbitrary nodes and edges, quite another to do something useful with them.