Parameterized computation theory has developed rapidly over the last two decades. In
theoretical computer science, it has attracted considerable attention for its theoretical value …

Given a digraph G=(V, E), the k-path partition problem aims to find a minimum collection of
vertex-disjoint directed paths, of order at most k, to cover all the vertices. The problem has …

A 3-path vertex cover in a graph is a vertex subset C such that every path of three vertices
contains at least one vertex from C. The parameterized 3-path vertex cover problem asks …

Let P ℓ denote a path in a graph G=(V, E) with ℓ vertices. A vertex cover P ℓ set C in G is a
vertex subset such that every P ℓ in G has at least a vertex in C. The Vertex Cover P ℓ …

In parameterized complexity, it is well-known that a parameterized problem is fixed-
parameter tractable if and only if it has a kernel—an instance equivalent to the input …

We introduce the balanced crown decomposition that captures the structure imposed on
graphs by their connected induced subgraphs of a given size. Such subgraphs are a …

Measure & Conquer is an approach helpful for designing branching algorithms. A key point
in the approach is how to design the measure. Given a graph G=(V, E) G=(V, E) and an …

Over the past decades, various metrics have emerged in graph theory to grasp the complex
nature of network vulnerability. In this paper, we study two specific measures:(weighted) …

Abstract The Almost Induced Matching problem asks whether we can delete at most k
vertices from the input graph such that each vertex in the remaining graph has a degree …

Consider a graph G. A subset of vertices, F, is called a vertex cover P_t P t (VCP_t VCP t) set
if every path of order t contains at least one vertex in F. Finding a minimum VCP_t VCP t set …