TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 18421

Algorithmic Enumeration: Output-sensitive, Input-Sensitive, Parameterized, Approximative

( Oct 14 – Oct 19, 2018 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/18421

Organizers

Contact



Schedule

Motivation

About fifty years ago, NP-completeness became the lens through which computer science views computationally hard (decision and optimization) problems. In the last decades, various new approaches to solve NP-hard problems exactly have attracted a lot of attention, among them parameterized and exact exponential-time algorithms, typically dealing with decision and optimization problems.

While optimization is ubiquitous in computer science and many application areas, relatively little is known about enumeration within the `Algorithms and Complexity' community. Fortunately, there has been important algorithmic research dedicated to enumeration problems in various fields of computer science, as, e.g., artificial intelligence and data mining, in natural sciences, engineering, and social sciences.

Enumeration problems require to list all wanted objects of the input as, e.g., particular subsets of the vertex or edge set of a given graph, or particular satisfying assignments of logical expressions. Contrary to decision, optimization, and even counting problems, the output length of enumeration problems is often exponential in the size of the input and cannot be neglected. This motivates the classical approach in enumeration, now called output-sensitive, which measures running time in (input and) output length, and asks for output-polynomial algorithms and algorithms of polynomial delay. This approach has been studied since a long time and has produced its own important open questions, among them the question whether the minimal transversals of a hypergraph can be enumerated in output-polynomial time. This longstanding and challenging question has triggered a lot of research. It is open for more than fifty years and most likely the best known open problem in algorithmic enumeration.

Recently, as a natural extension to research in exact exponential-time algorithms, a new approach, called input-sensitive, which measures the running time in the input length, has found growing interest. Due to the number of objects to enumerate (in the worst case), the corresponding algorithms have exponential running time. So far branching algorithms are a major tool. Input-sensitive enumeration is strongly related to lower and upper combinatorial bounds on the maximum number of objects to be enumerated for an input of given size. Such bounds can be achieved via input-sensitive enumeration algorithms but also by the use of combinatorial (non-algorithmic) means.

The area of algorithmic enumeration is in a nascent state though has a huge potential due to theoretical challenges and practical applications. While output-sensitive enumeration has a long history, input-sensitive enumeration has been initiated only recently. Natural and promising approaches like using parameterized or approximative approaches have not been explored yet to their full capacities.

Principal goals of our Dagstuhl Seminar are to increase the visibility of algorithmic enumeration within (theoretical) computer science and to contribute to establishing it as an area of `Algorithms and Complexity'. The seminar will bring together researchers within the algorithms community, other fields of computer science and computer engineering, as well as researchers working on enumeration problems in other application areas, in particular biology. Besides the people already working with enumeration, we invited researchers from other fields of computer science. In particular, we invited researchers who are interested in parameterized complexity, approximation, and different aspects of counting problems. The aim is to accelerate developments and discuss new directions including algorithmic tools and hardness proofs.

Copyright Henning Fernau, Petr A. Golovach, Dieter Kratsch, and Marie-France Sagot

Summary

About fifty years ago, NP-completeness became the lens through which Computer Science views computationally hard (decision and optimization) problems. In the last decades various new approaches to solve NP-hard problems exactly have attracted a lot of attention, among them parameterized and exact exponential-time algorithms, typically dealing with decision and optimization problems.

While optimization is ubiquitious in computer science and many application areas, relatively little is known about enumeration within the "Algorithms and Complexity" community. Fortunately there has been important algorithmic research dedicated to enumeration problems in various fields of Computer Science, as, e.g., Artificial Intelligence and Data Mining, in Natural Sciences Engineering and Social Sciences.

Enumeration problems require to list all wanted objects of the input as, e.g., particular subsets of the vertex or edge set of a given graph or particular satisfying assignments of logical expressions. Contrary to decision, optimization and even counting problems, the output length of enumeration problems is often exponential in the size of the input and cannot be neglected. This motivates the classical approach in enumeration, now called output-sensitive, which measures running time in (input and) output length, and asks for output-polynomial algorithms and algorithms of polynomial delay. This approach has been studied since a long time and has produced its own important open questions, among them the question whether the minimal transversals of a hypergraph can be enumerated in output-polynomial time. This longstanding and challenging question has triggered a lot of research. It is open for more than fifty years and most likely the best known open problem in algorithmic enumeration.

Recently as a natural extension on research in exact exponential-time algorithms, a new approach, called input-sensitive, which measures the running time in the input length, has found growing interest. Due to the number of objects to enumerate (in the worst case), the corresponding algorithms have exponential running time. So far branching algorithms are a major tool. Input-sensitive enumeration is strongly related to lower and upper combinatorial bounds on the maximum number of objects to be enumerated for an input of given size. Such bounds can be achieved via input-sensitive enumeration algorithms but also by the use of combinatorial (non-algorithmic) means.

The area of algorithmic enumeration is in a nascent state, though it has a huge potential due to theoretical challenges and practical applications. While output-sensitive enumeration has a long history, input-sensitive enumeration has been initiated only recently. Natural and promising approaches like using parameterized or approximative approaches have not been explored yet in their full capacities.

The principal goals of our Dagstuhl seminar were to increase the visibility of algorithmic enumeration within (Theoretical) Computer Science and to contribute to establishing it as an area of "Algorithms and Complexity". The seminar brought together researchers within the algorithms community, other fields of Computer Science and Computer Engineering, as well as researchers working on enumeration problems in other application areas, in particular, in Biology. Besides the people already working with enumeration, researchers from other fields of Computer Science were invited. In particular, researchers who are interested in Parameterized Complexity and different aspects of counting problems were participating in the seminar. The aim was to accelerate developments and discuss new directions including algorithmic tools and hardness proofs.

The seminar collected 44 participants from 13 countries. The participants presented their recent results in 18 invited and contributed talks. Open problems were discussed in several open problem and discussion sessions.

Copyright Marie-France Sagot, Dieter Kratsch, Henning Fernau, and Petr A. Golovach

Participants
  • Faisal N. Abu-Khzam (Lebanese American University - Beirut, LB) [dblp]
  • Ricardo Andrade (University Claude Bernard - Lyon, FR) [dblp]
  • Cristina Bazgan (University Paris-Dauphine, FR) [dblp]
  • Daniel Binkele-Raible (BEONTRA - Karlsruhe, DE) [dblp]
  • Andreas Björklund (Lund University, SE) [dblp]
  • Oscar Defrain (Université Clermont Auvergne - Aubiere, FR) [dblp]
  • Arnaud Durand (Paris Diderot University, FR) [dblp]
  • Martin Dyer (University of Leeds, GB) [dblp]
  • Khaled M. Elbassioni (Masdar Institute - Abu Dhabi, AE) [dblp]
  • Michael R. Fellows (University of Bergen, NO) [dblp]
  • Henning Fernau (Universität Trier, DE) [dblp]
  • Fedor V. Fomin (University of Bergen, NO) [dblp]
  • Serge Gaspers (UNSW - Sydney, AU) [dblp]
  • Petr A. Golovach (University of Bergen, NO) [dblp]
  • Benjamin Gras (University of Orleans, FR) [dblp]
  • Anne-Sophie Himmel (TU Berlin, DE) [dblp]
  • Leandro Ishi Soares de Lima (University Claude Bernard - Lyon, FR) [dblp]
  • Giuseppe F. Italiano (LUISS University, IT) [dblp]
  • Mamadou Moustapha Kanté (Université Clermont Auvergne - Aubiere, FR) [dblp]
  • Petteri Kaski (Aalto University, FI) [dblp]
  • Mathieu Liedloff (University of Orleans, FR) [dblp]
  • Daniel Lokshtanov (University of California - Santa Barbara, US) [dblp]
  • Kazuhisa Makino (University of Tokyo, JP) [dblp]
  • Alberto Marchetti-Spaccamela (Sapienza University of Rome, IT) [dblp]
  • Andrea Marino (University of Pisa, IT) [dblp]
  • Joao Marques-Silva (University of Lisbon, PT) [dblp]
  • Arnaud Mary (University Claude Bernard - Lyon, FR) [dblp]
  • Lhouari Nourine (University Clermont Auvergne, FR) [dblp]
  • Michal Pilipczuk (University of Warsaw, PL) [dblp]
  • Jean-Florent Raymond (TU Berlin, DE) [dblp]
  • Frances A. Rosamond (University of Bergen, NO) [dblp]
  • Günter Rote (FU Berlin, DE) [dblp]
  • Marie-France Sagot (University Claude Bernard - Lyon, FR) [dblp]
  • Saket Saurabh (Institute of Mathematical Sciences - Chennai, IN) [dblp]
  • Mohamed Yosri Sayadi (Université de Lorraine - Metz, FR) [dblp]
  • Martin Schirneck (Hasso-Plattner-Institut - Potsdam, DE) [dblp]
  • Blerina Sinaimeri (Université Lyon I, FR) [dblp]
  • Leen Stougie (CWI - Amsterdam, NL) [dblp]
  • Yann Strozecki (University of Versailles, FR) [dblp]
  • Takeaki Uno (National Institute of Informatics - Tokyo, JP) [dblp]
  • Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
  • Kunihiro Wasa (National Institute of Informatics - Tokyo, JP) [dblp]
  • Gerhard J. Woeginger (RWTH Aachen, DE) [dblp]
  • Petra Wolf (Universität Tübingen, DE) [dblp]

Classification
  • data structures / algorithms / complexity

Keywords
  • Output-sensitive enumeration
  • Input-sensitive enumeration
  • algorithms