A contraction sequence of a graph consists of iteratively merging two of its vertices until only
one vertex remains. The recently introduced twin-width graph invariant is based on …

We revisit two well-studied problems, Bounded Degree Vertex Deletion and Defective
Coloring, where the input is a graph G and a target degree Δ, and we are asked either to edit …

The complexity of problems involving global constraints is usually much more difficult to
understand than the complexity of problems only involving local constraints. A natural form …

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic
tractability: if the clique-width of a graph class G is bounded by a constant, a wide range of …

The goal of this work is to give precise bounds on the counting complexity of a family of
generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given …

The generic homomorphism problem, which asks whether an input graph $ G $ admits a
homomorphism into a fixed target graph $ H $, has been widely studied in the literature. In …

In this work we start the investigation of tight complexity bounds for connectivity problems
parameterized by cutwidth assuming the Strong Exponential-Time Hypothesis (SETH). Van …

We study connectivity problems from a fine-grained parameterized perspective. Cygan et
al.(TALG 2022) first obtained algorithms with single-exponential running time for connectivity …

Parameterized complexity seeks to use input structure to obtain faster algorithms for NP-
hard problems. This has been most successful for graphs of low treewidth: Many problems …

Graph Coloring is probably one of the most studied and famous problem in graph
algorithms. Exact methods fail to solve instances with more than few hundred vertices …