We introduce a new data structure for answering connectivity queries in undirected graphs
subject to batched vertex failures. Precisely, given any graph G and integer k, we can in …

We develop a framework for applying treewidth-based dynamic programming on graphs
with “hybrid structure”, ie, with parts that may not have small treewidth but instead possess …

Vertex-deletion problems have been at the heart of parameterized complexity throughout its
history. Here, the aim is to determine the minimum size (denoted by mod ℋ) of a modulator …

The elimination distance to some target graph property P is a general graph modification
parameter introduced by Bulian and Dawar. We initiate the study of elimination distances to …

In the literature on parameterized graph problems, there has been an increased effort in
recent years aimed at exploring novel notions of graph edit-distance that are more powerful …

For a hereditary graph class HH, the H H-elimination distance of a graph G is the minimum
number of rounds needed to reduce G to a member of HH by removing one vertex from each …

First-order logic (FO) can express many algorithmic problems on graphs, such as the
independent set and dominating set problem parameterized by solution size. However, FO …

Vertex deletion problems have been at the heart of numerous major advances in Algorithms
and Combinatorial Optimization, and especially so in the area of Parameterized Complexity …

The disjoint paths logic, FOL+ DP, is an extension of First-Order Logic (FOL) with the extra
atomic predicate dp k (x 1, y 1,…, xk, yk), expressing the existence of internally vertex …

Abstract Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance
in an effort to define new tractable parameterizations for graph problems and showed that …