Corelab Seminar

Elli Anastasiadi
Parameterized Complexity and Model Checking on Bounded Families of Graphs

We study the Model Checking Problem in a Parameterized Framework. The main objective is to determine the impact of an increment in our descriptive capabilities to the complexity of the Model Checking Problem over Graphs. There are some results in the field pointing to an inversely proportional relation but only as an intuitive notion not properly analyzed. This relation is presented through the different parameters that must be utilized to classify the Model Checking Problem for a logic as FPT. From a graph theoretic approach we aim to express the boundary between instances that can be checked quickly for a property in contrast with the ones cannot. To prove this relation we are using graph decompositions and properties of parameters to establish either a hierarchy between them or to derive a measurement of the cardinality of the bounded instances. From the Computability side, parameterized circuits are used to predict such relations between logics of different expressive power.