We study the problem of deleting the smallest set S of vertices (resp. edges) from a given
graph G such that the induced subgraph (resp. subgraph) G\S belongs to some class ℋ. We …

Let φ be a sentence of (monadic second-order logic with quantification over edge subsets
and counting modular predicates) over the signature of graphs. We present a dynamic data …

We consider the problem to find a set X of vertices (or arcs) with| X|≤ k in a given digraph G
such that D= G− X is an acyclic digraph. In its generality, this is Directed Feedback Vertex …

This work studies the parameterized complexity of finding secluded solutions to classical
combinatorial optimization problems on graphs such as finding minimum st separators …

Many problems are NP-hard and, unless P= NP, do not admit polynomial-time exact
algorithms. The fastest known exact algorithms exactly usually take time exponential in the …

Last update: September 1, 2014. This list contains a compilation of open problems from
recent Dagstuhl Seminars or Workshop on Kernels, as well as some problems mentioned in …

The H-free Edge Deletion problem asks, for a given graph G and integer k, whether it is
possible to delete at most k edges from G to make it H-free—that is, not containing H as an …

Abstract In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph G
and a positive integer k, and the objective is to decide whether G contains a minimal vertex …

We give a 5 kn O (1) fixed-parameter algorithm for determining whether a given undirected
graph on n vertices has a subset of at most k vertices whose deletion results in a tree. Such …

Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied
topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the …