On the (non-)existence of polynomial kernels for $P_l$-free edge modification problems

Sylvain Guillemot 1 Frédéric Havet 2 Christophe Paul 3 Anthony Perez 4
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Given a graph $G=(V,E)$ and a positive integer $k$, an edge modification problem for a graph property $\Pi$ consists in deciding whether there exists a set $F$ of pairs of $V$ of size at most $k$ such that the graph $H=(V,E\vartriangle F)$ satisfies the property $\Pi$. In the $\Pi$ \emph{edge-completion problem}, the set $F$ is constrained to be disjoint from $E$; in the $\Pi$ \emph{edge-deletion problem}, $F$ is a subset of $E$; no constraint is imposed on $F$ in the $\Pi$ \emph{edge-editing problem}. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity. When parameterized by the size $k$ of the set $F$, it has been proved that if $\Pi$ is an hereditary property characterized by a finite set of forbidden induced subgraphs, then the three $\Pi$ edge-modification problems are FPT. It was then natural to ask whether these problems also admit a polynomial kernel. Using recent lower bound techniques, Kratsch and Wahlström answered this question negatively. However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of $P_4$-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that \textsc{Parameterized cograph edge-modification} problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the \textsc{$P_l$-free edge-deletion} and the \textsc{$C_l$-free edge-deletion} problems for $l\geq 7$ and $l\geq 4$ respectively. Indeed, if they exist, then $NP \subseteq coNP / poly$.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2013, 65 (4), pp.900-926
Liste complète des métadonnées


https://hal.inria.fr/hal-00821612
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 16:06:29
Dernière modification le : samedi 10 juin 2017 - 01:12:28

Fichier

rr-cograph-kernel-2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00821612, version 1

Collections

Citation

Sylvain Guillemot, Frédéric Havet, Christophe Paul, Anthony Perez. On the (non-)existence of polynomial kernels for $P_l$-free edge modification problems. Algorithmica, Springer Verlag, 2013, 65 (4), pp.900-926. <hal-00821612>

Partager

Métriques

Consultations de
la notice

365

Téléchargements du document

97