An introduction to algorithms and complexity of counting and enumeration problems
Arnaud Durand
Université Paris Cité
Abstract:
Counting and enumerating are important tasks in algorithms: the former amounts to determine how many solutions has a given instance of a problem while the latter tries to generate one by one every such solutions. If the complexity of counting problems is an old field of theoretical computer science, enumeration has emerged only in the last 15 years in domains such as graphs algorithms and data management. In this talk we will introduce, through examples, some challenging problems in these areas and presents complexity measures which, for the case of enumeration problems, noticeably differs from the usual measures used for decision or optimisation. Examples will be taken in different areas such as graphs and combinatorial algorithms but also query answering in database theory. We will also illustrate how concepts coming from graph and hypergraph decompositions, from Boolean and algebraic circuits complexity are often mobilized to prove lower bound or to design efficient algorithms in these settings.