Parameterized complexity/multivariate complexity algorithmics is an exciting field of modern
algorithm design and analysis, with a broad range of theoretical and practical aspects that …

We consider the following well-known problem, which is called the disjoint paths problem.
For a given graph G and a set of k pairs of terminals in G, the objective is to find k vertex …

Given a graph G=(V, E) G=(V,E) and a subset of its vertices V′⊆ VV^′⊆V, the subgraph
induced by V′ V^′ in G is that with vertex set V′ V^′ and edge set E′ E^′ formed by …

In the PLANAR DISJOINT PATHS problem, one is given an undirected planar graph with a
set of k vertex pairs \left(s_i,t_i\right) and the task is to find k pairwise vertex-disjoint paths …

At the core of the seminal Graph Minor Theory of Robertson and Seymour is a powerful
theorem which describes the structure of graphs excluding a fixed minor. This result is used …

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms :
Shortest Cycle Through Specified Elements Page 1 Shortest Cycle Through Specified Elements …

Partial Cover problems are optimization versions of fundamental and well-studied problems
like Vertex Cover and Dominating Set. Here one is interested in covering (or dominating) the …

We give the first linear kernels for Dominating Set and Connected Dominating Set problems
on graphs excluding a fixed graph H as a minor. In other words, we give polynomial time …

One approach to confronting computational hardness is to try to understand the contribution
of various parameters to the running time of algorithms and the complexity of computational …

Abstract The Disjoint Paths Problem asks, given a graph G and a set of pairs of terminals (s
1, t 1),…,(sk, tk), whether there is a collection of k pairwise vertex-disjoint paths linking si and …