Corelab Seminar
2018-2019
Elli Anastasiadi
Parameterized Complexity and Model Checking on Bounded Families of Graphs
Abstract.
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.