ParaDeStruct: Complexity and approximability of counting problems through structural, descriptive, and parameterized methods

Funded by PEVE 2020

 

Principal Investigator:

Aristeidis Pagourtzis

Host Institution:

National Technical University of Athens

Project Number:

65/2283

Duration:

27 months (29/1/2021 - 27/4/2023)

Budget:

15,000 Euros

Project description

The objective of this project is to study the computational complexity of counting the number of solutions of combinatorial problems. Among the most well-studied counting problems are those that have an easy decision version, as these are essentially the only ones that may admit efficient algorithms for exact or approximate solving. Our research team has provided a structural characterization of a wide class of such problems, by proposing a novel model of computation which gave rise to the complexity class TotP. The main goal of this project is to analyze properties of TotP, and various of its subclasses, using tools from structural, descriptive, and parameterized complexity theories.

We will study classes of counting problems with an easy decision version and natural problems lying in them with respect to their approximability. We will explore the relationship between these classes and the class of approximable problems. We are also interested in the study of hard counting problems such that the corresponding decision problem can be solved by a randomized polynomial-time algorithm (it is in the class RP). Efficient randomized algorithms (fpras) for such natural counting problems will be examined.

Parameterized complexity will be used to adress specific counting problems and either design algorithms for them (FPT or FPTRAS), or, show hardness of counting problems (W[1]- or #W[1]-hardness).

From the perspective of descriptive complexity, our major objective is to determine the class that captures TotP. Complementarily, we will give logical characterizations of other classes containing hard counting problems with an easy decision version.

Research Team

Publications

Ph.D. Theses

Dissemination

Some research results of the project were presented in the International Joint Conference On Theoretical Computer Science (IJTCS 2021), the 16th Athens Colloquium on Algorithms and Complexity (ACAC 2021), the Young researcher's forum of the 23rd International Symposium on Fundamentals of Computation Theory (FCT 2021),the 33rd Nordic Workshop on Programming Theory (NWPT 2022), The New York Colloquium on Algorithms and Complexity (NYCAC 2022), The New York Colloquium on Algorithms and Complexity (NYCAC 2021), the 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022), the Logic Colloquium 2022, and the 17th Athens Colloquium on Algorithms and Complexity (ACAC 2022).