This paper settles the computational complexity of model checking of several extensions of
the monadic second order (MSO) logic on two classes of graphs: graphs of bounded …

Powerful results from the theory of integer programming have recently led to substantial
advances in parameterized complexity. However, our perception is that, except for Lenstra's …

Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central
topic of study in parameterized complexity. A main aim of research in this area is to …

Vertex Integrity is a graph measure which sits squarely between two more well-studied
notions, namely vertex cover and tree-depth, and that has recently gained attention as a …

We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system
$(V,\mathcal {F},\mathcal {B}) $ with two families $\mathcal {F},\mathcal {B} $ of subsets of …

We study the model checking problem of an extended MSO with local and global cardinality
constraints, called MSO Lin GL, introduced recently by Knop et al.(Log Methods Comput Sci …

Courcelle's celebrated theorem states that all MSO-expressible properties can be decided in
linear time on graphs of bounded treewidth. Unfortunately, the hidden constant implied by …

Abstract We study the Length-Bounded Cut problem for special graph classes and from a
parameterized complexity viewpoint. Here, we are given a graph G, two vertices s and t, and …

Selection of a group of representatives satisfying certain fairness constraints, is a commonly
occurring scenario. Motivated by this, we initiate a systematic algorithmic study of a\emph …

Powerful results from the theory of integer programming have recently led to substantial
advances in parameterized complexity. However, our perception is that, except for Lenstra's …