Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new user(Sub)linear kernels for edge modification problems towards structured graph classes
71
0
0.0
(
0
)
Added by
Gabriel Bathie
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Gabriel Bathie
Ask ChatGPT about the research
No Arabic abstract
In a (parameterized) graph edge modification problem, we are given a graph $G$, an integer $k$ and a (usually well-structured) class of graphs $mathcal{G}$, and ask whether it is possible to transform $G$ into a graph $G in mathcal{G}$ by adding and/or removing at most $k$ edges. Parameterized graph edge modification problems received considerable attention in the last decades. In this paper, we focus on finding small kernels for edge modification problems. One of the most studied problems is the Cluster Editing problem, in which the goal is to partition the vertex set into a disjoint union of cliques. Even if this problem admits a $2k$ kernel [Cao, 2012], this kernel does not reduce the size of most instances. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graphs are very structured (such as a partition into cliques for instance). We prove, as far as we know, the first sublinear kernel for an edge modification problem. Namely, we show that Clique + Independent Set Deletion, which is a restriction of Cluster Deletion, admits a kernel of size $O(k/log k)$. We also obtain small kernels for several other edge modification problems. We prove that Split Addition (and the equivalent Split Deletion) admits a linear kernel, improving the existing quadratic kernel of Ghosh et al. [Ghosh et al., 2015]. We complement this result by proving that Trivially Perfect Addition admits a quadratic kernel (improving the cubic kernel of Guo [Guo, 2007]), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under ETH.
rate research
Read More
In an edge modification problem, we are asked to modify at most $k$ edges to a given graph to make the graph satisfy a certain property. Depending on the operations allowed, we have the completion problems and the edge deletion problems. A great amount of efforts have been devoted to understanding the kernelization complexity of these problems. We revisit several well-studied edge modification problems, and develop improved kernels for them: begin{itemize} item a $2 k$-vertex kernel for the cluster edge deletion problem, item a $3 k^2$-vertex kernel for the trivially perfect completion problem, item a $5 k^{1.5}$-vertex kernel for the split completion problem and the split edge deletion problem, and item a $5 k^{1.5}$-vertex kernel for the pseudo-split completion problem and the pseudo-split edge deletion problem. end{itemize} Moreover, our kernels for split completion and pseudo-split completion have only $O(k^{2.5})$ edges. Our results also include a $2 k$-vertex kernel for the strong triadic closure problem, which is related to cluster edge deletion.
Let $H$ be a fixed graph. Given a graph $G$ and an integer $k$, the $H$-free edge modification problem asks whether it is possible to modify at most $k$ edges in $G$ to make it $H$-free. Sandeep and Sivadasan (IPEC 2015) asks whether the paw-free completion problem and the paw-free edge deletion problem admit polynomial kernels. We answer both questions affirmatively by presenting, respectively, $O(k)$-vertex and $O(k^4)$-vertex kernels for them. This is part of an ongoing program that aims at understanding compressibility of $H$-free edge modification problems.
In general, a graph modification problem is defined by a graph modification operation $boxtimes$ and a target graph property ${cal P}$. Typically, the modification operation $boxtimes$ may be vertex removal}, edge removal}, edge contraction}, or edge addition and the question is, given a graph $G$ and an integer $k$, whether it is possible to transform $G$ to a graph in ${cal P}$ after applying $k$ times the operation $boxtimes$ on $G$. This problem has been extensively studied for particilar instantiations of $boxtimes$ and ${cal P}$. In this paper we consider the general property ${cal P}_{{phi}}$ of being planar and, moreover, being a model of some First-Order Logic sentence ${phi}$ (an FOL-sentence). We call the corresponding meta-problem Graph $boxtimes$-Modification to Planarity and ${phi}$ and prove the following algorithmic meta-theorem: there exists a function $f:Bbb{N}^{2}toBbb{N}$ such that, for every $boxtimes$ and every FOL sentence ${phi}$, the Graph $boxtimes$-Modification to Planarity and ${phi}$ is solvable in $f(k,|{phi}|)cdot n^2$ time. The proof constitutes a hybrid of two different classic techniques in graph algorithms. The first is the irrelevant vertex technique that is typically used in the context of Graph Minors and deals with properties such as planarity or surface-embeddability (that are not FOL-expressible) and the second is the use of Gaifmans Locality Theorem that is the theoretical base for the meta-algorithmic study of FOL-expressible problems.
153 -
Pavel Dvov{r}ak
, Duv{s}an Knop (Department ofn Applied Mathematics Charles University Prague
2016
We show that it is possible to use Bondy-Chvatal closure to design an FPT algorithm that decides whether or not it is possible to cover vertices of an input graph by at most k vertex disjoint paths in the complement of the input graph. More precisely, we show that if a graph has tree-width at most w and its complement is closed under Bondy-Chvatal closure, then it is possible to bound neighborhood diversity of the complement by a function of w only. A simpler proof where tree-depth is used instead of tree-width is also presented.
A graph is said to be a Konig graph if the size of its maximum matching is equal to the size of its minimum vertex cover. The Konig Edge Deletion problem asks if in a given graph there exists a set of at most k edges whose deletion results in a Konig graph. While the vertex version of the problem (Konig vertex deletion) has been shown to be fixed-parameter tractable more than a decade ago, the fixed-parameter-tractability of the Konig Edge Deletion problem has been open since then, and has been conjectured to be W[1]-hard in several papers. In this paper, we settle the conjecture by proving it W[1]-hard. We prove that a variant of this problem, where we are given a graph G and a maximum matching M and we want a k-sized Konig edge deletion set that is disjoint from M, is fixed-parameter-tractable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
