Lorentz Center - Enumeration Algorithms Using Structure from 24 Aug 2015 through 28 Aug 2015
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    Enumeration Algorithms Using Structure
    from 24 Aug 2015 through 28 Aug 2015


A. Descriptions and aims of workshop


Enumeration is at the heart of Computer Science. Traditional enumeration algorithms use an output-sensitive time analysis. Recently exact exponential time enumeration algorithms using an input-sensitive analysis have been emerging. The main goal of the workshop was to bring the two communities together. Another goal was to discus and study the use of structural input properties when constructing enumeration algorithms.


B. Tangible outcome


The major and long time open problem in algorithmic enumeration is the question whether the minimal transversals of a hypergraph can be enumerated by an output-polynomial algorithm.

Recently it was shown that this question is equivalent to the question whether the minimal dominating sets of a graph can be enumerated by an output-polynomial algorithms. The later problem has been studied for many graph classes. More such results are to be expected.

A major question in input-sensitive enumeration mentioned various times at Leiden was solved recently: the number of minimal connected dominating sets of a graph on n vertices is smaller than 2^n.


C. Scientific breakthrough


Many interesting talks and discussions. However nothing to rank scientific breakthrough.


D.  Aha  moments


While the methods used by the two communities turned out to be very different, input-sensitive and output-sensitive enumeration algorithms can be combined sometimes such as to obtain a kind of optimal enumeration algorithm.


E. Workshop


The format of the workshop was perfect for our purposes. The many invited talks and the tutorials allowed to share the knowledge of the two communities. There are more researchers with publications on both types of enumeration algorithms now. The french enumeration community has now an ANR project (ANR = French Research Agency) concentrating on enumeration on graphs and hypergraphs which started in October 2015. One of the ideas of the project is to organize another enumeration workshop at Leiden.


F. Other comments


We were happy with the Lorentz Center and the help in organization, administration etc. we obtained. We compiled a technical report of open problems at the University of Utrecht.