ﻻ يوجد ملخص باللغة العربية
{sc Directed Feedback Vertex Set (DFVS)} is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the {sc ${cal H}$-free SCC Deletion} problem. Here, one is given a digraph $D$, an integer $k$ and the objective is to decide whether there is a vertex set of size at most $k$ whose deletion leaves a digraph where every strong component excludes graphs in the fixed finite family ${cal H}$ as (not necessarily induced) subgraphs. When ${cal H}$ comprises only the digraph with a single arc, then this problem is precisely DFVS. Our main result is a proof that this problem is fixed-parameter tractable parameterized by the size of the deletion set if ${cal H}$ only contains rooted graphs or if ${cal H}$ contains at least one directed path. Along with generalizing the fixed-parameter tractability result for DFVS, our result also generalizes the recent results of G{o}ke et al. [CIAC 2019] for the {sc 1-Out-Regular Vertex Deletion} and {sc Bounded Size Strong Component Vertex Deletion} problems. Moreover, we design algorithms for the two above mentioned problems, whose running times are better and match with the best bounds for {sc DFVS}, without using the heavy machinery of shadow removal as is done by G{o}ke et al. [CIAC 2019].
Graph-modification problems, where we add/delete a small number of vertices/edges to make the given graph to belong to a simpler graph class, is a well-studied optimization problem in all algorithmic paradigms including classical, approximation and p
The quest for colorful components (connected components where each color is associated with at most one vertex) inside a vertex-colored graph has been widely considered in the last ten years. Here we consider two variants, Minimum Colorful Components
We consider the problems of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the result of the modification satisfies some property definable in first-order logic. We establish a number of sufficie
We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q>1 and a graph G, the goal is to find a coloring of the edges of G with the maximu
A cactus is a connected graph that does not contain $K_4 - e$ as a minor. Given a graph $G = (V, E)$ and integer $k ge 0$, Cactus Vertex Deletion (also known as Diamond Hitting Set) is the problem of deciding whether $G$ has a vertex set of size at m