(Sub)linear Kernels for Edge Modification Problems Toward Structured Graph Classes

Autor: Gabriel Bathie, Nicolas Bousquet, Yixin Cao, Yuping Ke, Théo Pierron
Přispěvatelé: École normale supérieure de Lyon (ENS de Lyon), Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Department of Computing, Polytechnic University, Hong Kong, RGC grant 15201317, RGC grant 15226116, NSFC grant 61972330, ANR-18-CE40-0032,GrR,Reconfiguration de Graphes(2018)
Rok vydání: 2022
Předmět:
Zdroj: Algorithmica
Algorithmica, 2022, 84 (11), pp.3338-3364. ⟨10.1007/s00453-022-00969-1⟩
ISSN: 1432-0541
0178-4617
DOI: 10.1007/s00453-022-00969-1
Popis: International audience; In a (parameterized) graph edge modification problem, we are given a graph G, an integer k and a (usually well-structured) class G of graphs, and asked whether it is possible to transform G into a graph G ′ ∈ 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 a 2k-vertex kernel exists for Cluster Editing, this kernel does not reduce the size of the instance in most cases. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graph class is 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 first show that Cluster Deletion admits a 2k-vertex kernel as Cluster Editing, improving the previous 4kvertex kernel. We prove that (Pseudo-)Split Completion (and the equivalent (Pseudo-)Split Deletion) admits a linear kernel, improving the existing quadratic kernel. We also prove that Trivially Perfect Completion admits a quadratic kernel (improving the cubic kernel), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under the Exponential Time Hypothesis.
Databáze: OpenAIRE
Externí odkaz: