On the (Non-)Existence of Polynomial Kernels for Pl -Free Edge Modification Problems

Abstract : Given a graph G = (V , E) and an integer k, an edge modification problem for a graph property Π consists in deciding whether there exists a set of edges F of size at most k such that the graph H = (V , E △ F ) satisfies the property Π. In the Π edge-completion problem, the set F of edges is constrained to be disjoint from E; in the Π edge-deletion problem, F is a subset of E; no constraint is imposed on F in the Π edge-edition 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 edge set F , It has been proved that (Cai, IPL:58(4)-1996) if Π is an hereditary property characterized by a finite set of forbidden induced subgraph, then the three Π edge-modification problems are fixed-parameter tractable. It was then natural to ask (Cai, IWPEC 2006) whether these Π edge-modification problems also admit a polynomial size kernel (i.e. any instance (G, k) can be reduced in polynomial time to an equivalent instance (G′ , k′ ) with size bounded by a polynomial in k). Using recent lower bound techniques, Kratsch and Wahlstr¨om (IWPEC 2009) answered this question negatively. However, the problem remains open on many natural graph classes characterized by forbidden induced subgraph. It is a challenging question to characterized for which type of graph properties, the parameterized edge-modification problems have polynomial kernels. Kratsch and Wahlstr¨om asked whether the result holds when the forbidden subgraphs are paths and pointed out that the problem is already open in the case of P4 -free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that parameterized cograph edge modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for Pl -free graphs and Cl -free graph for large enough l.
Type de document :
Communication dans un congrès
IPEC'10: International Symposium on Parameterized and Exact Computation, France. 12 p., 2010, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00533519
Contributeur : Christophe Paul <>
Soumis le : dimanche 7 novembre 2010 - 08:08:49
Dernière modification le : vendredi 9 février 2018 - 19:00:03

Identifiants

  • HAL Id : lirmm-00533519, version 1

Collections

Citation

Sylvain Guillemot, Christophe Paul, Anthony Perez. On the (Non-)Existence of Polynomial Kernels for Pl -Free Edge Modification Problems. IPEC'10: International Symposium on Parameterized and Exact Computation, France. 12 p., 2010, Lecture Notes in Computer Science. 〈lirmm-00533519〉

Partager

Métriques

Consultations de la notice

86