Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Parameterized Complexity of Deletion to $mathcal{H}$-free Strong Components
291
0
0.0
(
0
)
Added by
Rian Neogi
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
{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].
rate research
Read More
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 parameterized complexity. Specifically, graph-deletion problems, where one needs to delete at most $k$ vertices to place it in a given non-trivial hereditary (closed under induced subgraphs) graph class, captures several well-studied problems including {sc Vertex Cover}, {sc Feedback Vertex Set}, {sc Odd Cycle Transveral}, {sc Cluster Vertex Deletion}, and {sc Perfect Deletion}. Investigation into these problems in parameterized complexity has given rise to powerful tools and techniques. While a precise characterization of the graph classes for which the problem is {it fixed-parameter tractable} (FPT) is elusive, it has long been known that if the graph class is characterized by a {it finite} set of forbidden graphs, then the problem is FPT. In this paper, we initiate a study of a natural variation of the problem of deletion to {it scattered graph classes} where we need to delete at most $k$ vertices so that in the resulting graph, each connected component belongs to one of a constant number of graph classes. A simple hitting set based approach is no longer feasible even if each of the graph classes is characterized by finite forbidden sets. As our main result, we show that this problem is fixed-parameter tractable (FPT) when the deletion problem corresponding to each of the finite classes is known to be FPT and the properties that a graph belongs to each of the classes is expressible in CMSO logic. When each graph class has a finite forbidden set, we give a faster FPT algorithm using the well-known techniques of iterative compression and important separators.
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 (MCC) and Maximum Edges in transitive Closure (MEC), introduced in 2011 in the context of orthology gene identification in bioinformatics. The input of both MCC and MEC is a vertex-colored graph. MCC asks for the removal of a subset of edges, so that the resulting graph is partitioned in the minimum number of colorful connected components; MEC asks for the removal of a subset of edges, so that the resulting graph is partitioned in colorful connected components and the number of edges in the transitive closure of such a graph is maximized. We study the parameterized and approximation complexity of MCC and MEC, for general and restricted instances. For MCC on trees we show that the problem is basically equivalent to Minimum Cut on Trees, thus MCC is not approximable within factor $1.36 - varepsilon$, it is fixed-parameter tractable and it admits a poly-kernel (when the parameter is the number of colorful components). Moreover, we show that MCC, while it is polynomial time solvable on paths, it is NP-hard even for graphs with constant distance to disjoint paths number. Then we consider the parameterized complexity of MEC when parameterized by the number $k$ of edges in the transitive closure of a solution (the graph obtained by removing edges so that it is partitioned in colorful connected components). We give a fixed-parameter algorithm for MEC paramterized by $k$ and, when the input graph is a tree, we give a poly-kernel.
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 sufficient and necessary conditions on the quantification pattern of the first-order formula phi for the problem to be fixed-parameter tractable or to admit a polynomial kernel.
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 maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q>1, and has been well-studied from the point of view of approximation. Our main focus is the case when q=2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.
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 most $k$ whose removal leaves a forest of cacti. The current best deterministic parameterized algorithm for this problem was due to Bonnet et al. [WG 2016], which runs in time $26^kn^{O(1)}$, where $n$ is the number of vertices of $G$. In this paper, we design a deterministic algorithm for Cactus Vertex Deletion, which runs in time $17.64^kn^{O(1)}$. As a straightforward application of our algorithm, we give a $17.64^kn^{O(1)}$-time algorithm for Even Cycle Transversal. The idea behind this improvement is to apply the measure and conquer analysis with a slightly elaborate measure of instances.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
